AT_arc224_c.Ascending Labels

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.

给你一个包含 $N$ 个顶点和 $M$ 条边的连通简单无向图。顶点编号为 $1,2,\ldots,N$，第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。

请构造一个整数序列 $A=(A_1,A_2,\ldots,A_N)$，使其满足以下所有条件：

• 对每个顶点 $v$，均有 $0 \le A_v \le N$；
• $A_1 = 0$；
• 对除顶点 $1$ 外的每个顶点 $v$，恰好存在一个与 $v$ 相邻的顶点 $w$，使得 $A_w = A_v - 1$。

在本题的约束条件下，可以证明至少存在一个满足上述所有条件的整数序列。若存在多个满足条件的序列，则输出任意一个即可。

共给出 $T$ 组测试数据，请对每组数据求解。

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$

输入从标准输入给出，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例：

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

每个测试用例的格式如下：

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

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$

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

对每个测试用例，按以下格式输出一个满足条件的整数序列 $A$：

$A_1$ $A_2$ $\dots$ $A_N$

Sample 1 Explanation:
This input contains three test cases.

For the first test case, consider setting $A=(0,2,1,2,1,2)$.

• For vertex $1$, $A_1=0$.
• For vertex $2$, there is only one adjacent vertex $w$ satisfying $A_w=A_2-1$, which is vertex $5$.
• For vertex $3$, there is only one adjacent vertex $w$ satisfying $A_w=A_3-1$, which is vertex $1$.
• For vertex $4$, there is only one adjacent vertex $w$ satisfying $A_w=A_4-1$, which is vertex $3$.
• For vertex $5$, there is only one adjacent vertex $w$ satisfying $A_w=A_5-1$, which is vertex $1$.
• For vertex $6$, there is only one adjacent vertex $w$ satisfying $A_w=A_6-1$, which is vertex $3$.

Thus, this integer sequence $A$ satisfies the conditions in the problem statement.

Additionally, setting $A=(0,3,1,2,2,2)$ also satisfies the conditions, so the output 0 3 1 2 2 2 is also accepted.

The figure below shows, for each test case in the sample output, the vertex number $v$ outside each vertex and $A_v$ inside each vertex.

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.

样例 1 解释：
该输入包含三个测试用例。

对于第一个测试用例，考虑设定 $A=(0,2,1,2,1,2)$。

• 对于顶点 $1$，有 $A_1=0$。
• 对于顶点 $2$，满足 $A_w=A_2-1$ 的相邻顶点 $w$ 恰好只有一个，即顶点 $5$。
• 对于顶点 $3$，满足 $A_w=A_3-1$ 的相邻顶点 $w$ 恰好只有一个，即顶点 $1$。
• 对于顶点 $4$，满足 $A_w=A_4-1$ 的相邻顶点 $w$ 恰好只有一个，即顶点 $3$。
• 对于顶点 $5$，满足 $A_w=A_5-1$ 的相邻顶点 $w$ 恰好只有一个，即顶点 $1$。
• 对于顶点 $6$，满足 $A_w=A_6-1$ 的相邻顶点 $w$ 恰好只有一个，即顶点 $3$。

因此，该整数序列 $A$ 满足题目描述中的条件。

此外，设定 $A=(0,3,1,2,2,2)$ 同样满足条件，故输出 0 3 1 2 2 2 也被接受。

下图展示了样例输出中每个测试用例的图示：每个顶点外部标注其顶点编号 $v$，内部标注对应的 $A_v$ 值。

约束条件

• $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$
• 若 $i \neq j$，则 $(U_i,V_i) \neq (U_j,V_j)$。
• 给定图是连通的。
• 所有输入中 $N$ 的总和不超过 $3 \times 10^5$。
• 所有输入中 $M$ 的总和不超过 $3 \times 10^5$。
• 所有输入值均为整数。