Starry Sky Parade

Una and you want to make a constellation from $N$ stars.

First, Una creates a blueprint, which is an undirected graph whose vertices are the $N$ stars numbered from $1$ to $N$. She always creates it using the following process.

Initially, only one star exists. She then adds the remaining $N-1$ stars one at a time in an arbitrary order. Whenever a star is added, she chooses one of the following two operations.

• Connect the new star to every star that already exists.
• Connect the new star to none of the stars that already exist.

After the blueprint is complete, you assign each star $i$ an integer brightness $A_i$ between $1$ and $N$. Two distinct stars $u$ and are connected by light if and only if

Assign brightnesses $A_1,A_2,\ldots,A_N$ 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:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print $N$ integers $A_1,A_2,\ldots,A_N$ satisfying the condition on one line.

• $1\leq T\leq10\,000$.
• $1\leq N\leq100\,000$.
• $0\le M\le$.