You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ARC108C] Keep Graph Connected

题目描述

给定一个 $n$ 个点 $m$ 条边的连通无向图（没有自环但是可能有重边），第 $i$ 条边连接 $u_i,v_i(u_i\not=v_i)$，它自身有一个编号 $c_i$。
现在可以在每个点上写上一个介于 $1 \sim n$ 的数，记作 $d_i$。
定义一条边是合法的，当且仅当它连接的两个点的 $d_{u_i},d_{v_i}$ 中仅有一个等于 $c_i$。最后，图中不合法的边将被删除。
定义一个图是好的，当且仅当删去不合法的边后，图仍然连通。确定是否有一种写数的方法使得图是好的。如果存在，输出任意一种方案，否则输出 No。

输入格式

第一行两个整数 $n,m$ ，接下来 $m$ 行每行三个整数 $u_i,v_i,c_i$。

输出格式

如果存在一种写数方案使得图是好的，输出 $n$ 行，每行一个整数 $d_i$ 表示一种写数方案，你可以输出任意一种。否则输出 No。

样例 #1

样例输入 #1

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

样例输出 #1

1
2
1

数据范围

• $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$

样例解释 1

- 顶点 $1,2,3$ 的值分别为 $1,2,1$，则第 $1,2,4$ 条边被保留，图仍然连通。