← 返回题目列表

AtCoder · arc108_c

C. 保持图表连接

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

分数: 500 点

问题陈述

给定一个无向连通图 N 顶点编号 1 to N,和 M 边编号 1 to M。 给定的图可能包含多边但不包含自环。

每条边之间都有一个整数标签 1 和 N (含)。 边缘 i 有一个标签 c_i,它连接 Vertex u_i 和 v_i 双向。

Snuke 将在之间写入一个整数 1 和 N (含)在每个顶点上(多个顶点可能写有相同的整数),然后只保留满足以下条件的边,删除其他边。

状况:让 x 和 y 是写在作为边的端点的顶点上的整数。 正是 之一 x 和 y 等于边的标签。

我们称之为在顶点上写入整数的方法 好 当(且仅当)在删除不满足上述条件的边后图仍然是连通的。确定是否存在一种书写整数的好方法,如果存在则提出一种这样的方法。

约束

  • 2 \leq N \leq 10^5
  • N-1 \leq M \leq 2 \times 10^5
  • 1 \leq u_i,v_i,c_i \leq N
  • 给定的图是连通的并且没有自环。

输入

输入由标准输入按以下格式给出:

N M
u_1 v_1 c_1
\vdots
u_M v_M c_M

输出

如果没有好的整数写入方法,请打印 No。 否则,打印 N 行。的 i- 第行应包含写在 Vertex 上的整数 i。 任何书写整数的好方法都会被接受。


示例输入 1

3 4
1 2 1
2 3 2
3 1 3
1 3 1

示例输出 1

1
2
1
  • 我们写 顶点上的 1, 2,和 1 在顶点上 1, 2,和 3。
  • 边缘 1 连接顶点 1 和 2,其标签为 1.
    • 仅写入 Vertex 上的整数 1 等于标签,因此这条边不会被删除。
  • 边缘 2 连接顶点 2 和 3,其标签为 2.
    • 仅写入 Vertex 上的整数 2 等于标签,因此这条边不会被删除。
  • 边缘 3 连接顶点 1 和 3,其标签为 3.
    • 顶点上写的两个整数与标签不同,因此这条边将被删除。
  • 边缘 4 连接顶点 1 和 3,其标签为 1.
    • 顶点上写的两个整数都等于标签,因此这条边将被删除。
  • 后沿 3 和 4 被删除,图形仍然是连通的,所以这是一种写整数的好方法。