There is a circle drawn on the ground. The circle has $$$n$$$ equally spaced marks on its perimeter. The $$$i$$$-th mark is said to be adjacent to the $$$(i-1)$$$-th and $$$(i+1)$$$-th marks (if they exist). Marks $$$1$$$ and $$$n$$$ are adjacent as well.
$$$n$$$ ferrets numbered form $$$1$$$ to $$$n$$$ will perform a dance on this circle. Initially, the $$$a_i$$$-th ferret is standing on the $$$i$$$-th mark. They will dance for $$$2025!^{2025!}$$$ rounds. If a ferret stands on mark $$$i$$$ at the beginning of a round, it will move to mark $$$p_i$$$ during that round.
Some pairs of ferrets are best friends and don't like being too far from each other. A pair of best friends is happy if they stand in adjacent marks during any round. The pairs of ferrets that are best friends have a particular characteristic: if we consider ferrets as nodes and the best friend relations as edges, the resulting graph forms a tree.
Find two permutations $$$[a_1,a_2,\dots,a_n]$$$ and $$$[p_1,p_2,\dots,a_n]$$$ such that all the pairs of best friends are happy. It can be shown that it is always possible to find such permutations with the given constraints.
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5)$$$ – the number of ferrets.
The following $$$n-1$$$ lines contain the pairs of ferrets that are best friends. It it guaranteed that the best friends relations form a tree.
Print the $$$n$$$ space-separated integers $$$a_1,a_2,\dots,a_n$$$ in the first line of the output.
Print the $$$n$$$ space-separated integers $$$p_1,p_2,\dots,p_n$$$ in the second line.
51 22 33 44 5
1 2 3 4 5 1 2 3 4 5
63 44 56 11 24 1
3 4 5 6 1 2 2 3 1 6 4 5
