Subway

jiefangxuanyan and yiyi cat are universally acknowledged model couples. Once jiefangxuanyan has time, he takes a train to yiyi cat’s city and meet her. This time, as usual, jiefangxuanyan gets out from the railway station, and enters the subway, only to find that the subway stations of the whole city changes their names!

As a direction idiot, jiefangxuanyan felt helpless with this situation. He called yiyi cat for help. Because the subway map is so complicated, she can’t remember it either. Fortunately, only the names of the stations changed, the structure of subway lines is the same. So she picks out the old map to make a mapping.

But mapping such a confused subway map is definitely a difficult task. So she has to use the computer. Unfortunately, she just spilt wonton soup into her computer. So, yiyi cat asked you for help, hoping you can help her with this problem.

The subway in the city forms a tree, with N subway stations and N-1 subway lines. Any pair of stations are connected with one or more subway lines. You need to find a bijective mapping from the old names to the new names, that for each pair of stations connected by exactly one line in the old map, their new names are also connected by exactly one line in the new map.

The input has multiple test cases, please process to the end of file.

For each test case, the first line is an integer $N (1\leq N\leq 100000)$.

In the following $N-1$ lines, each line has two space-separated string, as two stations connected by one line in the old map.

In the following $N-1$ lines, each line has two space-separated string, as two stations connected by one line in the new map.

Station names are no longer than 10 characters, and only consists of lowercase letters (a~z).

For each test case, output $N$ lines.

Each line consists two space-separated string, as the old name and its corresponding new name.

Both the names appeared in the old and new subway map should appear exactly once in the output.

You can output the names in any order. And if there are multiple valid mappings, output any one.

Names in the old map and the new map may be the same, but this does not mean these two stations are the same.

3
a b
b c
b a
a c

b a
a b
c c

HIT

2016 Multi-University Training Contest 1