← 返回题目列表

AtCoder · arc224_c

C. 升序标签

中文机器翻译题面 查看原题

分数: 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 在每个顶点内。