{"problem":{"name":"J. Дружелюбный интерфейс","description":{"content":"После получения разноцветного диплома об окончании факультета Высокой Магии и Колдовства Марсианского Галактического Университета, Пафнутий готовится поступать в аспирантуру. На лето он устроился сист","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10059J"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nВ первой строке входного файла находится единственное целое число 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.\n\n## Выходные Данные\n\nВ выходной файл выведите «_YES_», если решение для данного случая существует, и «_NO_» в противном случае.\n\n## Примеры\n\nВходные данные51 22 33 44 523 14 235 21 12 2Выходные данныеYESВходные данные51 22 33 42 522 14 221 23 1Выходные данныеNO\n\n## Примечание\n\nВ первом примере требуется передать сообщение от компьютера 3 к компьютеру 1, а также от компьютера 4 к компьютерам 2 и 5. Передача сообщения от 4 к 2 затрёт сообщение, находящееся в ячейке памяти машины 3, поэтому необходимо сначала выполнить передачу от 3 к 1, а затем от 4 к 2. Передачу сообщения от компьютера 4 к компьютеру 5 можно выполнить когда угодно.Во втором примере передача сообщения от компьютера 4 к компьютеру 1 затрёт содержимое ячеек памяти машин 2 и 3, поэтому успешная пересылка невозможна. Компьютер 5 не может быть использован ни в одной передаче сообщения.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10059J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}