| VK Cup 2018 - Раунд 1 |
|---|
| Закончено |
В стране Боба N городов, соединенных дорогами. Между некоторыми парами городов можно проехать на общественном транспорте. Есть две конкурирующие компании: Бобавто возит пассажиров на автобусах, а Бобжд управляет пассажирскими поездами. Чтобы проехать из города A в город B, пассажир сначала должен выбрать вид транспорта, который он будет использовать (автобус или поезд), и затем отправиться в путь. Для каждой пары городов существует ровно два способа добраться из одного города в другой, не посещая ни один город дважды: один способ использует автобусы, другой — поезда. Кроме того, никакая пара городов не соединена одновременно автобусной линией и железной дорогой напрямую.
У вас есть схемы обеих сетей. К сожалению, каждая компания использует различные названия для одних и тех же городов. А именно, автобусная компания нумерует города от 1 до N, а железнодорожная — от N + 1 до 2N. Найдите какое-либо возможное соответствие между этими нумерациями такое, что никакая пара городов не соединена одновременно автобусным и железнодорожным маршрутом напрямую. Обратите внимание на то, что различным городам на одной схеме должны соответствовать различные города другой схемы.
Первая строка содержит одно целое число N (2 ≤ N ≤ 10000) — количество городов.
Следующие N - 1 строк описывают маршрутную сеть Бобавто. Каждая строка содержит два целых числа u и v (1 ≤ u, v ≤ N), означающие, что есть прямой автобусный маршрут между городами u и v.
Следующие N - 1 строк описывают железнодорожную сеть Бобжд. Каждая строка содержит два целых числа u и v (N + 1 ≤ u, v ≤ 2N), означающие, что есть прямой железнодорожный маршрут между городами u и v.
Если решения нет, выведите единственную строку, содержащую слово «No».
Если решение существует, выведите две строки. В первой строке выведите слово «Yes». Во второй строке выведите N целых чисел P1, P2, ..., PN (N + 1 ≤ Pi ≤ 2N) — соответствие между двумя схемами. А именно, для i ≠ j должно выполняться Pi ≠ Pj, и для всех автобусных маршрутов (i, j) не должно быть прямого железнодорожного маршрута (Pi, Pj).
Если существует несколько решений, выведите любое.
4
1 2
2 3
3 4
5 6
6 7
7 8
Yes
6 8 5 7
4
1 2
2 3
3 4
5 6
5 7
5 8
No
7
1 2
1 3
1 4
1 5
5 6
6 7
8 9
9 10
10 11
11 12
12 13
13 14
Yes
9 14 11 12 13 10 8
Первый пример показан на рисунке (автобусные линии красные, железнодорожные — синие):
