E. Panda-monium
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Michael has gotten the internship of a lifetime! He will be working (unpaid, obviously) at Thomas' zoo in the red panda enclosure.

The enclosure can be described as a tree of $$$n$$$ nodes, rooted at node $$$1$$$. Each node contains a house which has exactly one red panda in it. Every afternoon, Michael will be in charge of organized nap-time for the pandas, which involves all $$$n$$$ red pandas reaching the root of the tree to take a nap. It works as follows:

  • In one second, Michael may let any number of pandas out of their homes. Then, all pandas that have been let out of their home, other than those at the root, climb up one node in the tree towards the root. The process repeats until Michael has placed all $$$n$$$ pandas.
  • If two red pandas ever occupy the same node other than the root, they will start a fight, so this cannot happen.

Note that the panda that lives in node $$$1$$$ must still be let out of its house to join the other pandas (and hug them).

Michael wants to accomplish this task as fast as possible, so he can eat his lunchtime Raisin Brain cereal. What is the minimum time (in seconds) that it will take for Michael to finish placing all pandas, and what is a possible way he can achieve it? Note that Michael will be finished once he places the last panda, not when all pandas reach the root.

Input

The problem has $$$t$$$ ($$$1 \leq t \leq 10^4$$$) independent test cases.

For each test case, the first line will contain $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$). The next $$$n - 1$$$ lines contain the edges of the tree. Each line will have two integers, $$$u$$$ and $$$v$$$, meaning there is an edge between nodes $$$u$$$ and $$$v$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the minimum number of seconds it will take Michael to place the pandas.

Then, in a new line, print $$$i$$$ integers, where the $$$i$$$-th integer is the second during which Michael should let out the panda in node $$$i$$$. If there are multiple possible solutions, print any.

Example
Input
2
4
1 2
3 2
4 1
5
1 2
1 3
3 4
5 3
Output
1
1 1 1 1 
2
1 1 1 1 2
Note

For the first test case, Michael can release all pandas at once.

For the second test case, Michael can't release all pandas at once since the pandas at nodes $$$4$$$ and $$$5$$$ will start a fight.

Problem Credits: Allen Wu