После получения разноцветного диплома об окончании факультета Высокой Магии и Колдовства Марсианского Галактического Университета, Пафнутий готовится поступать в аспирантуру. На лето он устроился системным администратором в контору по заготовке чистых стёкол и прямых досок, рассчитывая, что работа почти не будет отвлекать его от подготовки к вступительным экзаменам. Но вместо ожидаемого погружения в мир прикладной магии (и сапёра) Пафнутию каждый день приходится сталкиваться со сложными задачами!
В компании работает N сотрудников, каждый из которых использует ровно один персональный компьютер. Машины объединены в сеть с помощью N - 1 соединений, разрешающих парам компьютеров обмениваться данными в любом направлении. Сеть спроектирована таким образом, что между любой парой компьютеров существует ровно один кратчайший (по числу соединений) путь.
К сожалению, сетевые технологии не только помогают в работе и учёбе, но и предоставляют неограниченные возможности для бесцельной траты времени, поэтому сеть бóльшую часть времени находится в выключенном состоянии. Активация происходит лишь на две секунды раз в пять часов, чтобы переслать между сотрудниками накопившиеся сообщения.
Сообщения передаются при помощи интерфейса, который ещё помнит, как весело жужжала старушка БЭСМ-6. Его работа происходит строго по следующим правилам:
Гарантируется, что каждый компьютер в сети является получателем не более чем одного сообщения, причем никогда не является и отправителем, и получателем одновременно. Как этого добивается администрация — остается загадкой.
Пафнутию нравится решать в уме задачу выбора правильной последовательности пересылок, но правильного ответа может и не существовать. Он просит вас написать программу, которая по описанию конфигурации сети и готовых к отправке сообщений определит, существует ли последовательность пересылок, приводящая к успешному завершению работы интерфейса передачи сообщений. Сама последовательность системного администратора при этом не интересует.
В первой строке входного файла находится единственное целое число N — количество компьютеров. Следующие N - 1 строк содержат пары чисел vi и ui, каждая из которых означает наличие соединения между парой компьютеров с данными номерами. 1 ≤ N ≤ 4 000, 1 ≤ vi, ui ≤ N, vi ≠ ui. Гарантируется, что между любой парой вершин существует путь, состоящий из данных соединений.
Следующая строка содержит единственное целое число S — количество отправляемых сообщений. Следующие S строк содержат по два целых числа si и sidi — номер машины, отправляющей сообщение, и уникальный идентификатор сообщения. 1 ≤ S ≤ N, 1 ≤ si, sidi ≤ N. Гарантируется, что все si и sidi уникальны.
Далее следует строка, содержащая единственное целое число K — количество компьютеров, принимающих сообщения. Следующие K строк содержат по два целых числа ti и tidi — номер компьютера и идентификатор принимаемого сообщения. 1 ≤ S + K ≤ N, 1 ≤ ti, tidi ≤ N. Гарантируется, что все ti уникальны и что ti ≠ sj для любых i и j. Гарантируется, что для любого i найдётся j такое, что tidi = sidj.
В выходной файл выведите «_YES_», если решение для данного случая существует, и «_NO_» в противном случае.
В первом примере требуется передать сообщение от компьютера 3 к компьютеру 1, а также от компьютера 4 к компьютерам 2 и 5. Передача сообщения от 4 к 2 затрёт сообщение, находящееся в ячейке памяти машины 3, поэтому необходимо сначала выполнить передачу от 3 к 1, а затем от 4 к 2. Передачу сообщения от компьютера 4 к компьютеру 5 можно выполнить когда угодно.
Во втором примере передача сообщения от компьютера 4 к компьютеру 1 затрёт содержимое ячеек памяти машин 2 и 3, поэтому успешная пересылка невозможна. Компьютер 5 не может быть использован ни в одной передаче сообщения.
## Входные Данные
В первой строке входного файла находится единственное целое число N — количество компьютеров. Следующие N - 1 строк содержат пары чисел vi и ui, каждая из которых означает наличие соединения между парой компьютеров с данными номерами. 1 ≤ N ≤ 4 000, 1 ≤ vi, ui ≤ N, vi ≠ ui. Гарантируется, что между любой парой вершин существует путь, состоящий из данных соединений.Следующая строка содержит единственное целое число S — количество отправляемых сообщений. Следующие S строк содержат по два целых числа si и sidi — номер машины, отправляющей сообщение, и уникальный идентификатор сообщения. 1 ≤ S ≤ N, 1 ≤ si, sidi ≤ N. Гарантируется, что все si и sidi уникальны.Далее следует строка, содержащая единственное целое число K — количество компьютеров, принимающих сообщения. Следующие K строк содержат по два целых числа ti и tidi — номер компьютера и идентификатор принимаемого сообщения. 1 ≤ S + K ≤ N, 1 ≤ ti, tidi ≤ N. Гарантируется, что все ti уникальны и что ti ≠ sj для любых i и j. Гарантируется, что для любого i найдётся j такое, что tidi = sidj.
## Выходные Данные
В выходной файл выведите «_YES_», если решение для данного случая существует, и «_NO_» в противном случае.
## Примеры
Входные данные51 22 33 44 523 14 235 21 12 2Выходные данныеYESВходные данные51 22 33 42 522 14 221 23 1Выходные данныеNO
## Примечание
В первом примере требуется передать сообщение от компьютера 3 к компьютеру 1, а также от компьютера 4 к компьютерам 2 и 5. Передача сообщения от 4 к 2 затрёт сообщение, находящееся в ячейке памяти машины 3, поэтому необходимо сначала выполнить передачу от 3 к 1, а затем от 4 к 2. Передачу сообщения от компьютера 4 к компьютеру 5 можно выполнить когда угодно.Во втором примере передача сообщения от компьютера 4 к компьютеру 1 затрёт содержимое ячеек памяти машин 2 и 3, поэтому успешная пересылка невозможна. Компьютер 5 не может быть использован ни в одной передаче сообщения.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of computers.
Let $ T = (V, E) $ be a tree with $ V = \{1, 2, \dots, N\} $ and $ |E| = N - 1 $.
Let $ S \in \mathbb{Z}^+ $ be the number of senders.
Let $ \mathcal{P} = \{(s_i, d_i) \mid i \in \{1, \dots, S\}\} $ be the set of message send requests, where $ s_i \in V $ is the sender and $ d_i \in V $ is the destination of message $ i $.
Let $ K \in \mathbb{Z}^+ $ be the number of receivers.
Let $ \mathcal{R} = \{(t_j, r_j) \mid j \in \{1, \dots, K\}\} $ be the set of message receive requests, where $ t_j \in V $ is the receiver and $ r_j \in \mathbb{Z} $ is the message ID.
Assume:
- Each computer is either a sender, a receiver, or neither, but not both.
- For every message ID $ m $, there is exactly one sender $ s $ and one receiver $ t $ such that $ (s, m) \in \mathcal{P} $ and $ (t, m) \in \mathcal{R} $.
- Thus, $ \mathcal{P} $ and $ \mathcal{R} $ define a bijection between senders and receivers via message IDs: $ \sigma: \{s_1, \dots, s_S\} \to \{t_1, \dots, t_K\} $, where $ \sigma(s_i) = t_j \iff d_i = r_j $.
**Constraints**
1. $ 1 \le N \le 4000 $
2. $ 1 \le S \le N $, $ 1 \le K \le N $, $ S + K \le N $
3. All $ s_i $, $ t_j $ are distinct.
4. $ s_i \ne t_j $ for all $ i, j $.
5. The underlying graph $ T $ is a tree.
**Objective**
Determine whether there exists a sequence of point-to-point message transfers along tree edges such that:
- Each message $ m $ is routed from its sender $ s $ to its receiver $ t $ along the unique path in $ T $.
- At no time does a computer act as an intermediate node for a message unless it is not currently holding a message (i.e., no computer may store more than one message at a time).
- Messages are transferred one at a time, and each transfer moves a message along one edge.
- A message may only be transferred from a computer that currently holds it.
**Answer**
Output "YES" if such a sequence exists; otherwise, output "NO".