K. King and Zeroing
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

There are $$$n$$$ cities in some imaginary kingdom. All cities are connected by $$$n - 1$$$ bidirectional roads. The toll to drive a single road is exactly $$$1$$$ credit in each direction.

Recently citizens have started to wonder why it's so expensive to drive across the country. King has decided to make some roads free of charge. He wants to choose a single road for each city and make the toll in the outgoing direction free for everybody. His goal is to minimize the maximum total toll among all direct road trips from one city to another. You should help him!

Input

The first line contains a single positive integer $$$n$$$ ($$$2 \leq n \leq 200\,000$$$) — the number of cities in an imaginary kingdom.

Next $$$n - 1$$$ lines contain two positive integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$) — the description of $$$i$$$-th road, connecting cities $$$a_i$$$ and $$$b_i$$$.

Output

In the first line print a single integer $$$d$$$ — the minimum total toll which would be required to pay for the most expensive road trip from one city to the other.

In the next line print $$$n$$$ integers $$$e_i$$$ — the index of the road selected for the $$$i$$$-th city to be free of charge. If no road is selected for the $$$i$$$-th city print $$$e_i = -1$$$.

Examples
Input
4
1 2
1 3
1 4
Output
1
-1 1 2 3
Input
3
1 2
2 3
Output
1
1 -1 2