Задача №114151. Анархия в Берляндии
С незапамятных времен Берляндией правили добрые и справедливые цари, а власть передавалась по наследству. Но вот настали тяжёлые времена, по воле рока династия прервалась, и страна погрузилась в хаос. Некоторые города были захвачены враждующими друг с другом бандами головорезов, в других же городах какая-либо власть исчезла вовсе.
Всё началось с того, что в некоторых городах установилась власть преступных банд, причём под властью каждой из банд изначально оказалось ровно по одному городу. Каждая банда избрала в качестве столицы город своего первоначального зарождения. Начиная с того времени, каждый год ровно одна из банд решала расширить свои владения, захватывая некоторый город, до этого не бывший ни в чьём подчинении или находящийся под властью другой банды.
Для осуществления захвата вооружённый отряд данной банды выходил из своей столицы и двигался к выбранному городу, захватывая все города на своём пути. Также известно, что столицы всех банд были так серьёзно защищены, что через них невозможно было проехать (и уж тем более не могло идти речи об их захвате). Поэтому на пути от столицы банды-захватчика до выбранного города не могло быть столиц других банд.
Как уже неоднократно отмечалось различными историками, в описываемые времена в Берляндии было N городов, соединённых между собой N - 1 дорогой с двусторонним движением, при этом от каждого города можно было доехать до любого другого. Подобное устройство транспортной системы естественным образом налагало ограничения на возможные маршруты путешествия.
События эти происходили уже очень давно, а хроники тех лет были утрачены в вихре смутного времени. Теперь же к вам в руки попала карта Берляндии тех времён. Вы обнаружили, что на карте отмечены столицы каждой из банд, а также для каждого города указано, какая банда им владела на определённый момент времени (свободных городов к тому году уже не осталось).
Вычислите, при какой возможной последовательности захватов могло возникнуть описанное этой картой распределение контроля банд над городами, или же определите, что карта содержит ошибку, так как указанное на карте распределение власти банд над городами не могло быть получено с помощью последовательности описанных выше захватов. Более того, среди возможных ответов вам необходимо найти последовательность, состоящую из не более чем N захватов.
В первой строке входных данных через пробел указаны два целых числа N и M — количество городов на карте Берляндии и количество преступных банд ( 1 ≤ M ≤ N ≤ 300 000 ).
В следующих N - 1 строках описываются дороги Берляндии. Каждая строка содержит два различных целых числа a i и b i ( 1 ≤ a i , b i ≤ N ), обозначающих, что между городами с номерами a i и b i существовала дорога с двусторонним движением.
В следующей строке входных данных через пробел указаны M различных целых чисел c i ( 1 ≤ c i ≤ N ): согласно карте, в городе с номером c i находилась столица банды i .
В последней строке входных данных находятся N разделенных пробелами целых чисел d i , обозначающих, что город под номером i ( 1 ≤ i ≤ N ) отмечен на карте как находящийся под властью банды с номером d i ( 1 ≤ d i ≤ M ). Гарантируется, что d c i = i для всех i .
Если существует такая последовательность захватов, которая приводит к указанному на карте распределению контроля банд над городами, то в первой строке выведите слово « YES » (без кавычек). В следующей строке выведите единственное целое число S — длину найденной последовательности захватов (обратите внимание, должно выполняться неравенство 0 ≤ S ≤ N ). В следующих S строках выведите по два различных числа x i и y i — номера городов, являющихся столицей банды, захватывающей города в i -м году, и конечной целью захвата в i -м году соответственно.
Если же карта содержит ошибку и получить распределение контроля банд над городами, указанное на карте, невозможно, то в единственной строке вывода выведите слово « NO » (без кавычек).
Гарантируется, что если существует последовательность захватов, приводящая к указанному на карте распределению контроля банд над городами, то такое распределение контроля банд над городами всегда могло возникнуть не более чем за N лет.
Для удобства участников проверяющая программа не требует, чтобы на момент захвата города y i он не принадлежал банде, владеющей городом x i . Более того, разрешается выводить даже такие x i и y i , что все города на пути между ними принадлежат одной и той же банде. Обращаем ваше внимание, что это сделано исключительно для удобства участников. Все остальные требования к операциям захвата должны быть соблюдены.
Примером событий, приведших к картине, описанной в первом тесте, может служить следующая последовательность захватов:
- Первоначально в городах 1 и 2 образовалось по банде. Города 3 и 4 на этот момент никому не подвластны.
- В первый год первая банда отправилась захватывать город 4 , по пути установив контроль над городом 3 .
- Во второй год вторая банда отобрала контроль над городом 3 у первой банды.
Во втором примере не существует последовательности захватов, которая привела бы к описанной картине.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
4 2 1 3 2 3 3 4 1 2 1 2 2 1
YES 2 1 4 2 3
5 3 1 3 2 3 3 4 3 5 1 2 3 1 2 3 1 3
NO