{"raw_statement":[{"iden":"statement","content":"После получения разноцветного диплома об окончании факультета Высокой Магии и Колдовства Марсианского Галактического Университета, Пафнутий готовится поступать в аспирантуру. На лето он устроился системным администратором в контору по заготовке чистых стёкол и прямых досок, рассчитывая, что работа почти не будет отвлекать его от подготовки к вступительным экзаменам. Но вместо ожидаемого погружения в мир прикладной магии (и сапёра) Пафнутию каждый день приходится сталкиваться со сложными задачами!\n\nВ компании работает N сотрудников, каждый из которых использует ровно один персональный компьютер. Машины объединены в сеть с помощью N - 1 соединений, разрешающих парам компьютеров обмениваться данными в любом направлении. Сеть спроектирована таким образом, что между любой парой компьютеров существует ровно один кратчайший (по числу соединений) путь.\n\nК сожалению, сетевые технологии не только помогают в работе и учёбе, но и предоставляют неограниченные возможности для бесцельной траты времени, поэтому сеть бóльшую часть времени находится в выключенном состоянии. Активация происходит лишь на две секунды раз в пять часов, чтобы переслать между сотрудниками накопившиеся сообщения.\n\nСообщения передаются при помощи интерфейса, который ещё помнит, как весело жужжала старушка БЭСМ-6. Его работа происходит строго по следующим правилам:\n\nГарантируется, что каждый компьютер в сети является получателем не более чем одного сообщения, причем никогда не является и отправителем, и получателем одновременно. Как этого добивается администрация — остается загадкой.\n\nПафнутию нравится решать в уме задачу выбора правильной последовательности пересылок, но правильного ответа может и не существовать. Он просит вас написать программу, которая по описанию конфигурации сети и готовых к отправке сообщений определит, существует ли последовательность пересылок, приводящая к успешному завершению работы интерфейса передачи сообщений. Сама последовательность системного администратора при этом не интересует.\n\n \n\nВ первой строке входного файла находится единственное целое число N — количество компьютеров. Следующие N - 1 строк содержат пары чисел vi и ui, каждая из которых означает наличие соединения между парой компьютеров с данными номерами. 1 ≤ N ≤ 4 000, 1 ≤ vi, ui ≤ N, vi ≠ ui. Гарантируется, что между любой парой вершин существует путь, состоящий из данных соединений.\n\nСледующая строка содержит единственное целое число S — количество отправляемых сообщений. Следующие S строк содержат по два целых числа si и sidi — номер машины, отправляющей сообщение, и уникальный идентификатор сообщения. 1 ≤ S ≤ N, 1 ≤ si, sidi ≤ N. Гарантируется, что все si и sidi уникальны.\n\nДалее следует строка, содержащая единственное целое число K — количество компьютеров, принимающих сообщения. Следующие K строк содержат по два целых числа ti и tidi — номер компьютера и идентификатор принимаемого сообщения. 1 ≤ S + K ≤ N, 1 ≤ ti, tidi ≤ N. Гарантируется, что все ti уникальны и что ti ≠ sj для любых i и j. Гарантируется, что для любого i найдётся j такое, что tidi = sidj.\n\nВ выходной файл выведите «_YES_», если решение для данного случая существует, и «_NO_» в противном случае.\n\nВ первом примере требуется передать сообщение от компьютера 3 к компьютеру 1, а также от компьютера 4 к компьютерам 2 и 5. Передача сообщения от 4 к 2 затрёт сообщение, находящееся в ячейке памяти машины 3, поэтому необходимо сначала выполнить передачу от 3 к 1, а затем от 4 к 2. Передачу сообщения от компьютера 4 к компьютеру 5 можно выполнить когда угодно.\n\nВо втором примере передача сообщения от компьютера 4 к компьютеру 1 затрёт содержимое ячеек памяти машин 2 и 3, поэтому успешная пересылка невозможна. Компьютер 5 не может быть использован ни в одной передаче сообщения.\n\n"},{"iden":"входные данные","content":"В первой строке входного файла находится единственное целое число 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."},{"iden":"выходные данные","content":"В выходной файл выведите «_YES_», если решение для данного случая существует, и «_NO_» в противном случае."},{"iden":"примеры","content":"Входные данные51 22 33 44 523 14 235 21 12 2Выходные данныеYESВходные данные51 22 33 42 522 14 221 23 1Выходные данныеNO"},{"iden":"примечание","content":"В первом примере требуется передать сообщение от компьютера 3 к компьютеру 1, а также от компьютера 4 к компьютерам 2 и 5. Передача сообщения от 4 к 2 затрёт сообщение, находящееся в ячейке памяти машины 3, поэтому необходимо сначала выполнить передачу от 3 к 1, а затем от 4 к 2. Передачу сообщения от компьютера 4 к компьютеру 5 можно выполнить когда угодно.Во втором примере передача сообщения от компьютера 4 к компьютеру 1 затрёт содержимое ячеек памяти машин 2 и 3, поэтому успешная пересылка невозможна. Компьютер 5 не может быть использован ни в одной передаче сообщения."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of computers.  \nLet $ T = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, N\\} $ and $ |E| = N - 1 $.  \n\nLet $ S \\in \\mathbb{Z}^+ $ be the number of senders.  \nLet $ \\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 $.  \n\nLet $ K \\in \\mathbb{Z}^+ $ be the number of receivers.  \nLet $ \\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.  \n\nAssume:  \n- Each computer is either a sender, a receiver, or neither, but not both.  \n- 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} $.  \n- 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 $.  \n\n**Constraints**  \n1. $ 1 \\le N \\le 4000 $  \n2. $ 1 \\le S \\le N $, $ 1 \\le K \\le N $, $ S + K \\le N $  \n3. All $ s_i $, $ t_j $ are distinct.  \n4. $ s_i \\ne t_j $ for all $ i, j $.  \n5. The underlying graph $ T $ is a tree.  \n\n**Objective**  \nDetermine whether there exists a sequence of point-to-point message transfers along tree edges such that:  \n- Each message $ m $ is routed from its sender $ s $ to its receiver $ t $ along the unique path in $ T $.  \n- 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).  \n- Messages are transferred one at a time, and each transfer moves a message along one edge.  \n- A message may only be transferred from a computer that currently holds it.  \n\n**Answer**  \nOutput \"YES\" if such a sequence exists; otherwise, output \"NO\".","simple_statement":"You are given a tree with N nodes (computers) and N-1 edges. Some nodes are senders (each sends one unique message), some are receivers (each receives one unique message). Each message has an ID, and every sender’s message ID matches exactly one receiver’s message ID. Messages must be routed along the unique path between sender and receiver. A node can hold only one message at a time. When a message passes through a node, it overwrites whatever was there before.  \n\nDetermine if there exists an order to route all messages so that every message reaches its correct receiver without conflict — i.e., no message is lost because another message overwrote it on the path before it got there.  \n\nOutput \"YES\" if possible, \"NO\" otherwise.","has_page_source":false}