Задача №112694. Дружелюбный интерфейс
После получения разноцветного диплома об окончании факультета Высокой Магии и Колдовства Марсианского Галактического Университета, Пафнутий готовится поступать в аспирантуру. На лето он устроился системным администратором в контору по заготовке чистых стёкол и прямых досок, рассчитывая, что работа почти не будет отвлекать его от подготовки к вступительным экзаменам. Но вместо ожидаемого погружения в мир прикладной магии (и сапёра) Пафнутию каждый день приходится сталкиваться со сложными задачами!
В компании работает N сотрудников, каждый из которых использует ровно один персональный компьютер. Машины объединены в сеть с помощью N - 1 соединений, разрешающих парам компьютеров обмениваться данными в любом направлении. Сеть спроектирована таким образом, что между любой парой компьютеров существует ровно один кратчайший (по числу соединений) путь.
К сожалению, сетевые технологии не только помогают в работе и учёбе, но и предоставляют неограниченные возможности для бесцельной траты времени, поэтому сеть бóльшую часть времени находится в выключенном состоянии. Активация происходит лишь на две секунды раз в пять часов, чтобы переслать между сотрудниками накопившиеся сообщения.
Сообщения передаются при помощи интерфейса, который ещё помнит, как весело жужжала старушка БЭСМ-6. Его работа происходит строго по следующим правилам:
- На каждой машине имеется ячейка памяти, в которой в любой момент времени может находиться не более одного сообщения.
- Пока сеть выключена, любой сотрудник может создать сообщение для отправки коллегам. Для этого он помещает сообщение в ячейку памяти своего компьютера и задаёт список адресатов. Как только сеть активируется, возможность создания сообщений отключается и начинается их пересылка.
- Пересылка состоит из последовательного выполнения операций передачи сообщения от одного компьютера, на котором создано сообщение, к другому, который находится в списке адресатов. Определение порядка передачи всех сообщений и есть основная функция системного администратора в данном учреждении.
- В процессе передачи сообщения между компьютерами v и u оно обязательно будет записано в ячейки памяти всех компьютеров, расположенных на кратчайшем пути между v и u .
- Если после выполнения очередной операции пересылки все исходные сообщения находятся в ячейках памяти всех своих адресатов, то работа интерфейса передачи сообщений считается успешно выполненной и сеть снова выключается. Что находится в этот момент в ячейках памяти компьютеров, которым не было адресовано ни одного сообщения, не имеет значения.
Гарантируется, что каждый компьютер в сети является получателем не более чем одного сообщения, причем никогда не является и отправителем, и получателем одновременно. Как этого добивается администрация "— остается загадкой.
Пафнутию нравится решать в уме задачу выбора правильной последовательности пересылок, но правильного ответа может и не существовать. Он просит вас написать программу, которая по описанию конфигурации сети и готовых к отправке сообщений определит, существует ли последовательность пересылок, приводящая к успешному завершению работы интерфейса передачи сообщений. Сама последовательность системного администратора при этом не интересует.
В первой строке входного файла находится единственное целое число N — количество компьютеров. Следующие N - 1 строк содержат пары чисел v i и u i , каждая из которых означает наличие соединения между парой компьютеров с данными номерами. 1 ≤ N ≤ 4 000 , 1 ≤ v i , u i ≤ N , v i ≠ u i . Гарантируется, что между любой парой вершин существует путь, состоящий из данных соединений.
Следующая строка содержит единственное целое число S — количество отправляемых сообщений. Следующие S строк содержат по два целых числа s i и sid i — номер машины, отправляющей сообщение, и уникальный идентификатор сообщения. 1 ≤ S ≤ N , 1 ≤ s i , sid i ≤ N . Гарантируется, что все s i и sid i уникальны.
Далее следует строка, содержащая единственное целое число K — количество компьютеров, принимающих сообщения. Следующие K строк содержат по два целых числа t i и tid i — номер компьютера и идентификатор принимаемого сообщения. 1 ≤ S + K ≤ N , 1 ≤ t i , tid i ≤ N . Гарантируется, что все t i уникальны и что t i ≠ s j для любых i и j . Гарантируется, что для любого i найдётся j такое, что tid i = sid j .
В выходной файл выведите « YES », если решение для данного случая существует, и « NO » в противном случае.
В первом примере требуется передать сообщение от компьютера 3 к компьютеру 1, а также от компьютера 4 к компьютерам 2 и 5. Передача сообщения от 4 к 2 затрёт сообщение, находящееся в ячейке памяти машины 3, поэтому необходимо сначала выполнить передачу от 3 к 1, а затем от 4 к 2. Передачу сообщения от компьютера 4 к компьютеру 5 можно выполнить когда угодно.
Во втором примере передача сообщения от компьютера 4 к компьютеру 1 затрёт содержимое ячеек памяти машин 2 и 3, поэтому успешная пересылка невозможна. Компьютер 5 не может быть использован ни в одной передаче сообщения.
5 1 2 2 3 3 4 4 5 2 3 1 4 2 3 5 2 1 1 2 2
YES
5 1 2 2 3 3 4 2 5 2 2 1 4 2 2 1 2 3 1
NO