Una and you want to make a constellation from stars.
First, Una creates a blueprint, which is an undirected graph whose vertices are the stars numbered from to . She always creates it using the following process.
Initially, only one star exists. She then adds the remaining stars one at a time in an arbitrary order. Whenever a star is added, she chooses one of the following two operations.
After the blueprint is complete, you assign each star an integer brightness between and . Two distinct stars and are connected by light if and only if
Assign brightnesses so that the graph formed by light connections is exactly Una's blueprint.
It is guaranteed that a valid assignment exists for every input.
The input is given in the following format:
For each test case, print integers satisfying the condition on one line.
Each test case is given in the following format:
Each pair represents an edge between stars and . The graph has no self-loops or duplicate edges.
If several valid assignments exist, print any one of them.