Problem Statement

You are given a connected simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1,2,\ldots,N$, and the $i$-th edge connects vertices $U_i$ and $V_i$.

Construct one integer sequence $A=(A_1,A_2,\ldots,A_N)$ satisfying all of the following conditions.

• $0 \le A_v \le N$ for every vertex $v$.
• $A_1=0$.
• For every vertex $v$ other than vertex $1$, there is exactly one vertex $w$ adjacent to $v$ satisfying $A_w=A_v-1$.

It can be proved that under the constraints of this problem, there exists at least one integer sequence satisfying all of the above conditions. If there are multiple integer sequences satisfying the conditions, any of them will be accepted.

$T$ test cases are given; solve each of them.

Constraints

• $1 \le T \le 3 \times 10^4$
• $1 \le N \le 3 \times 10^5$
• $N-1 \le M \le 3 \times 10^5$
• $1 \le U_i < V_i \le N$
• $(U_i,V_i) \neq (U_j,V_j)$ if $i \neq j$.
• The given graph is connected.
• The sum of $N$ in each input is at most $3 \times 10^5$.
• The sum of $M$ in each input is at most $3 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$-th test case:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

For each test case, output an integer sequence $A$ satisfying the conditions in the following format:

A_1 A_2 \dots A_N