← 返回题目列表

Codeforces · 923/F

F. 公共服务

中文机器翻译题面 查看原题

Bob 的国家中有 N 个城市有公路相连。一些城市之间有公共交通相连。有两家相互竞争的运输公司——Boblines 运营巴士,Bobrail 运营火车。当乘客从A地旅行到B地时,总是先选择交通方式(公共汽车或火车),然后踏上旅程。对于每对城市,有两种方式可以在不多次访问任何城市的情况下在它们之间旅行 - 一种仅使用巴士路线,第二种仅使用火车路线。此外,没有一对城市同时有巴士路线和火车路线直接连接。

您已获取每个网络的计划。不幸的是,每家公司对同一城市使用不同的名称。更准确地说,公交公司使用 1 到 N 之间的整数对城市进行编号,而火车​​公司使用 N + 1 到 2N 之间的整数。找到这两种编号方案之间的一种可能的映射,使得没有一对城市同时通过巴士路线和火车路线直接连接。请注意,此映射必须将不同的城市映射到不同的城市。

输入

第一行包含一个整数 N (2 ≤ N ≤ 10000),城市数量。

接下来是 N - 1 行,代表 Boblines 的网络规划。每个包含两个整数u和v(1≤u,v≤N),意味着城市u和v之间有一条公交路线。

N - 1 行,代表 Bobrail 的网络规划。每个包含两个整数u和v(N + 1 ≤ u,v ≤ 2N),意味着城市u和v之间有一条火车路线。

输出

如果没有解决方案,则输出一行“否”。

如果存在解,则输出两行。第一行应该有“是”这个词。第二行应该有 N 个整数 P1, P2, ..., PN (N + 1 ≤ Pi ≤ 2N) - 两种编号方案之间的映射。更准确地说,对于 i ≠ j,应该是 Pi ≠ Pj,并且对于每条直达巴士路线 (i, j),(Pi, Pj) 之间没有直达火车路线。

如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

4
1 2
2 3
3 4
5 6
6 7
7 8

输出 #1

Yes
6 8 5 7

输入 #2

4
1 2
2 3
3 4
5 6
5 7
5 8

输出 #2

No

输入 #3

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

输出 #3

Yes
9 14 11 12 13 10 8

注意

第一个样本(红色为公交线路,蓝色为铁路线路):