分数: 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 被删除,图形仍然是连通的,所以这是一种写整数的好方法。