English · Original
Chinese · Translation
Formal · Original
There are _N_ cities in Bob's country connected by roads. Some pairs of cities are connected by public transport. There are two competing transport companies — **Boblines** operating buses and **Bobrail** running trains. When traveling from _A_ to _B_, a passenger always first selects the mode of transport (either bus or train), and then embarks on a journey. For every pair of cities, there are exactly two ways of how to travel between them without visiting any city more than once — one using only bus routes, and the second using only train routes. Furthermore, there is no pair of cities that is directly connected by both a bus route and a train route.
You obtained the plans of each of the networks. Unfortunately, each of the companies uses different names for the same cities. More precisely, the bus company numbers the cities using integers from 1 to _N_, while the train company uses integers between _N_ + 1 and 2_N_. Find one possible mapping between those two numbering schemes, such that no pair of cities is connected directly by both a bus route and a train route. Note that this mapping has to map different cities to different cities.
## Input
The first line contains an integer _N_ (2 ≤ _N_ ≤ 10000), the number of cities.
_N_ - 1 lines follow, representing the network plan of Boblines. Each contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _N_), meaning that there is a bus route between cities _u_ and _v_.
_N_ - 1 lines follow, representing the network plan of Bobrail. Each contains two integers _u_ and _v_ (_N_ + 1 ≤ _u_, _v_ ≤ 2_N_), meaning that there is a train route between cities _u_ and _v_.
## Output
If there is no solution, output a single line with the word "_No_".
If a solution exists, output two lines. On the first line, there should be the word "_Yes_". On the second line, there should be _N_ integers _P_1, _P_2, ..., _P__N_ (_N_ + 1 ≤ _P__i_ ≤ 2_N_) — the mapping between the two numbering schemes. More precisely, for _i_ ≠ _j_ it should be _P__i_ ≠ _P__j_, and for every direct bus route (_i_, _j_), there is no direct train route between (_P__i_, _P__j_).
If there are multiple solutions, you may print any of them.
[samples]
## Note
The first sample (bus lines in red and rail lines in blue):
Bob的国家有 #cf_span[N] 座城市，通过道路相连。某些城市对之间有公共交通连接。有两个竞争的运输公司——*Boblines* 运营公交车，*Bobrail* 运营火车。当从 #cf_span[A] 前往 #cf_span[B] 时，乘客首先选择交通方式（公交车或火车），然后开始旅程。对于每一对城市，恰好有两种方式可以在不重复访问任何城市的情况下旅行——一种仅使用公交路线，另一种仅使用火车路线。此外，不存在一对城市同时被公交路线和火车路线直接连接。
你获得了两家公司的网络计划。不幸的是，每家公司对同一座城市使用不同的编号。更准确地说，公交公司使用从 #cf_span[1] 到 #cf_span[N] 的整数对城市编号，而火车公司使用从 #cf_span[N + 1] 到 #cf_span[2N] 的整数。请找出一种可能的映射方案，将这两种编号体系对应起来，使得没有任何一对城市同时被公交路线和火车路线直接连接。注意，该映射必须将不同的城市映射到不同的城市。
第一行包含一个整数 #cf_span[N] (#cf_span[2 ≤ N ≤ 10000])，表示城市数量。
接下来 #cf_span[N - 1] 行表示 Boblines 的网络计划。每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ N])，表示城市 #cf_span[u] 和 #cf_span[v] 之间有一条公交路线。
接下来 #cf_span[N - 1] 行表示 Bobrail 的网络计划。每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[N + 1 ≤ u, v ≤ 2N])，表示城市 #cf_span[u] 和 #cf_span[v] 之间有一条火车路线。
如果没有解，请输出一行单词 "_No_"。
如果存在解，请输出两行。第一行输出单词 "_Yes_"。第二行输出 #cf_span[N] 个整数 #cf_span[P1, P2, ..., PN] (#cf_span[N + 1 ≤ Pi ≤ 2N]) —— 表示两种编号方案之间的映射。更准确地说，对于 #cf_span[i ≠ j]，应满足 #cf_span[Pi ≠ Pj]，且对于每条直接的公交路线 #cf_span[(i, j)]，都不存在直接的火车路线连接 #cf_span[(Pi, Pj)]。
如果有多个解，输出任意一个即可。
第一个样例（红色为公交线路，蓝色为铁路线路）：
## Input
第一行包含一个整数 #cf_span[N] (#cf_span[2 ≤ N ≤ 10000])，表示城市数量。#cf_span[N - 1] 行随后给出 Boblines 的网络计划，每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ N])，表示城市 #cf_span[u] 和 #cf_span[v] 之间有一条公交路线。#cf_span[N - 1] 行随后给出 Bobrail 的网络计划，每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[N + 1 ≤ u, v ≤ 2N])，表示城市 #cf_span[u] 和 #cf_span[v] 之间有一条火车路线。
## Output
如果没有解，请输出一行单词 "_No_"。如果存在解，请输出两行。第一行输出单词 "_Yes_"。第二行输出 #cf_span[N] 个整数 #cf_span[P1, P2, ..., PN] (#cf_span[N + 1 ≤ Pi ≤ 2N]) —— 表示两种编号方案之间的映射。更准确地说，对于 #cf_span[i ≠ j]，应满足 #cf_span[Pi ≠ Pj]，且对于每条直接的公交路线 #cf_span[(i, j)]，都不存在直接的火车路线连接 #cf_span[(Pi, Pj)]。如果有多个解，输出任意一个即可。
[samples]
## Note
第一个样例（红色为公交线路，蓝色为铁路线路）：
**Definitions**
Let $ N \in \mathbb{Z} $, $ 2 \leq N \leq 10000 $.
Let $ G_b = (V_b, E_b) $ be the bus network, where $ V_b = \{1, 2, \dots, N\} $ and $ E_b $ consists of $ N-1 $ undirected edges.
Let $ G_t = (V_t, E_t) $ be the train network, where $ V_t = \{N+1, N+2, \dots, 2N\} $ and $ E_t $ consists of $ N-1 $ undirected edges.
**Constraints**
1. $ G_b $ and $ G_t $ are both trees.
2. For every pair of distinct cities $ i, j \in V_b $, there is **exactly one** path in $ G_b $ and **exactly one** path in $ G_t $ between them (implied by tree structure).
3. No edge in $ G_b $ corresponds to an edge in $ G_t $ under the bijection we seek.
**Objective**
Find a bijection $ P: V_b \to V_t $, i.e., $ P(i) \in \{N+1, \dots, 2N\} $, such that:
- $ P $ is injective (hence bijective since $ |V_b| = |V_t| $),
- For every edge $ (i, j) \in E_b $, the edge $ (P(i), P(j)) \notin E_t $.
If no such bijection exists, output "_No_".
Otherwise, output "_Yes_" followed by the list $ P(1), P(2), \dots, P(N) $.
API Response (JSON)
{
"problem": {
"name": "F. Public Service",
"description": {
"content": "There are _N_ cities in Bob's country connected by roads. Some pairs of cities are connected by public transport. There are two competing transport companies — **Boblines** operating buses and **Bobra",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF923F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There are _N_ cities in Bob's country connected by roads. Some pairs of cities are connected by public transport. There are two competing transport companies — **Boblines** operating buses and **Bobra...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Bob的国家有 #cf_span[N] 座城市，通过道路相连。某些城市对之间有公共交通连接。有两个竞争的运输公司——*Boblines* 运营公交车，*Bobrail* 运营火车。当从 #cf_span[A] 前往 #cf_span[B] 时，乘客首先选择交通方式（公交车或火车），然后开始旅程。对于每一对城市，恰好有两种方式可以在不重复访问任何城市的情况下旅行——一种仅使用公交路线，另一种仅使用火...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ N \\in \\mathbb{Z} $, $ 2 \\leq N \\leq 10000 $. \nLet $ G_b = (V_b, E_b) $ be the bus network, where $ V_b = \\{1, 2, \\dots, N\\} $ and $ E_b $ consists of $ N-1 $ undirected edges....",
"is_translate": false,
"language": "Formal"
}
]
}