AT_arc224_c [ARC224C] Ascending Labels

给定一个连通的无向简单图，包含 $N$ 个顶点和 $M$ 条边。顶点编号为 $1,2,\ldots,N$，第 $i$ 条边连接了顶点 $U_i$ 和 $V_i$。 请构造一个整数序列 $A=(A_1,A_2,\ldots,A_N)$，满足以下所有条件： - 对于每个顶点 $v$，都有 $0 \leq A_v \leq N$。 - $A_1=0$。 - 对于除顶点 $1$ 以外的每个顶点 $v$，恰好存在一个与 $v$ 相邻的顶点 $w$，满足 $A_w=A_v-1$。 可以证明，在本题的约束条件下，至少存在一个满足要求的整数序列。如果存在多个满足条件的序列，输出任意一个都可以。 有 $T$ 组测试数据；请依次解决所有测试数据。

输入从标准输入读入，格式如下。其中 $\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$

输出 $T$ 行，第 $i$ 行为第 $i$ 组测试数据的答案。 对于每组测试数据，输出一个满足所有条件的整数序列 $A$，格式如下： > $A_1$ $A_2$ $\dots$ $A_N$

### 样例解释 1 该输入包含三组测试数据。 对于第一组测试数据，可以设 $A=(0,2,1,2,1,2)$。 - 对于顶点 $1$，$A_1=0$。 - 对于顶点 $2$，只有一个相邻顶点 $w$ 满足 $A_w = A_2 - 1$，即顶点 $5$。 - 对于顶点 $3$，只有一个相邻顶点 $w$ 满足 $A_w = A_3 - 1$，即顶点 $1$。 - 对于顶点 $4$，只有一个相邻顶点 $w$ 满足 $A_w = A_4 - 1$，即顶点 $3$。 - 对于顶点 $5$，只有一个相邻顶点 $w$ 满足 $A_w = A_5 - 1$，即顶点 $1$。 - 对于顶点 $6$，只有一个相邻顶点 $w$ 满足 $A_w = A_6 - 1$，即顶点 $3$。 因此，这个整数序列 $A$ 满足题意。 此外，设 $A=(0,3,1,2,2,2)$ 也满足所有条件，所以输出 `0 3 1 2 2 2` 也是正确的。 下图展示了样例输出中，每个顶点外围的编号 $v$ 以及内部的 $A_v$。  ### 数据范围 - $1 \leq T \leq 3 \times 10^4$ - $1 \leq N \leq 3 \times 10^5$ - $N-1 \leq M \leq 3 \times 10^5$ - $1 \leq U_i < V_i \leq N$ - $ (U_i, V_i) \neq (U_j, V_j) $，如果 $ i \neq j $ - 所给的图是连通的。 - 所有测试数据中 $N$ 的总和不超过 $3 \times 10^5$。 - 所有测试数据中 $M$ 的总和不超过 $3 \times 10^5$。 - 所有输入值均为整数。 由 ChatGPT 5 翻译