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
注意
第一个样本(红色为公交线路,蓝色为铁路线路):