Public Service
Contest: VK Cup 2018 - Round 1
Difficulty rating: 3200
Tags: constructive algorithms, graphs, trees

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 2N. 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 format:
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 ≤ 2N), meaning that there is a train route between cities u and v.

Output format:
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 P1, P2, ..., PN (N + 1 ≤ Pi ≤ 2N) — the mapping between the two numbering schemes. More precisely, for i ≠ j it should be Pi ≠ Pj, and for every direct bus route (i, j), there is no direct train route between (Pi, Pj).

If there are multiple solutions, you may print any of them.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
The first sample (bus lines in red and rail lines in blue):

Example input:
4
1 2
2 3
3 4
5 6
6 7
7 8

Example output:
Yes
6 8 5 7

Example input:
4
1 2
2 3
3 4
5 6
5 7
5 8

Example output:
No

Editorial:
For k ≥ 0, we call graph G a k-star, if we can remove k vertices to form a star, and we cannot remove k - 1 vertices to form a star. In this terminology, a 0-star is a star.
It should be rather obvious that if one of the graphs is a 0-star, then the answer is clearly No. This is because the minimum degree of a vertex in a tree is 1, and star has a vertex of degree N - 1, and the corresponding vertex in the merged graph would have degree at least N, which is clearly impossible.
Surprisingly, the answer is Yes in all other cases. We prove this by giving an explicit construction. There are three cases:
1. Assume that one of the graphs is 1-star. Without loss of generality let it be G. Denote v the vertex that can be removed to turn G into star, u its only neighbor, and w be the vertex of degree N - 2. In graph H, find any leaf and denote it w'. Let its only neighbour be u'. Furthermore, pick v' a vertex that is not adjacent to u' (such vertex always exists as H is not a star). Observe that mapping $$u \rightarrow u'$$, $$v \rightarrow v'$$ and $$w \rightarrow w'$$ does not introduce multiedges in the merged graph. Furthermore, all other edges in G are incident to w, but none of the unprocessed edges in H are incident to w'. We can thus map the remaining N - 3 vertices arbitrarily. Mapping a 1-star G (in red), to arbitrary tree H (in blue). See that there are no multiedges between u, v, w, no multiedges from u, v, w to the rest of the graph (since u, v and w' have no neighbours there), and no multiedges in the rest of the graph (since $${ G \setminus \{ u, v, w \} }$$ is a graph with zero edges).
2. N = 4 or N = 5: There are only five non-isomorphic trees on this many vertices. Two of them are 0-stars (for which the answer is No), two of them are 1-stars (that we handled in previous case). The only remaining graph is a path on five vertices. Two such graphs can always be merged together. For simplicity of implementation, we can simply try all 5! possible mappings.All trees on 4 or 5 vertices.
3. Otherwise, we use induction. In G, find two leaves u and v such that d(u, v) ≥ 3 and $${ G \setminus \{ u, v \} }$$ is not a star. This is always possible: either G is a 2-star, and then we can pick one of the neighbouring leaves of the vertex with highest degree and one other leaf, or we can pick any two leaves that are not adjacent to the same vertex. Do the same thing for H, finding u' and v'. Remove these pairs of vertices from the respective graphs and use induction to merge those smaller graphs. Now we can either map $$u \rightarrow u'$$, $$v \rightarrow v'$$ or $$u \rightarrow v^{\prime}$$, $$v \rightarrow u^{\prime}$$ — as only one of these mappings may introduce a multiedge.
The above is relatively simple to implement in $${\mathcal {O}}(n^{2})$$. To turn it into an $${\mathcal {O}}(n\log n)$$ algorithm, we need to maintain a few additional information about the graph. Furthemore, note that a graph G is a k-star if and only if the maximum degree is |G| - k - 1.
• The list vertices sorted by their degree, for instance using set of pairs. This is so that we can find the vertex with maximum degree easily, which is useful for testing k-starness.
• the set of vertices with a leaf neighbour, and
• the set of leaves neighbouring a given vertex, so that we can find the leaves quickly
Using the above, we can always find appropriate leaf and remove it in $${\mathcal {O}}(\log n)$$, which is sufficient.