分数: 500 点
问题陈述
给你一个连通的简单无向图 N 顶点和 M 边缘。 顶点已编号 1,2,\ldots,N,以及 i第一条边连接顶点 U_i 和 V_i.
构造一个整数序列 A=(A_1,A_2,\ldots,A_N) 满足以下所有条件。
- 0 \le A_v \le N 对于每个顶点 v.
- A_1=0.
- 对于每个顶点 v 顶点以外 1,只有一个顶点 w 毗邻 v 满意 A_w=A_v-1.
可以证明,在本问题的约束下,至少存在一个满足上述所有条件的整数序列。 如果有多个整数序列满足条件,则接受其中任何一个。
T 给出了测试用例;解决它们中的每一个。
约束
- 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.
- 给定的图形已连接。 每个输入中的
- 总和 N 最多为 3 \times 10^5.
- 总和 M 最多为 3 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \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
3 6 7 1 5 1 3 3 5 2 5 3 4 3 6 4 6 1 0 6 10 4 6 1 4 2 5 3 6 1 3 1 2 2 3 2 4 3 4 3 5
示例输出 1
0 2 1 2 1 2 0 0 3 2 1 3 3
此输入包含三个测试用例。
对于第一个测试用例,考虑设置 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 在每个顶点内。
