题目描述

给定一个包含 $N$ 个编号为 $1$ 到 $N$ 的顶点和 $M$ 条编号为 $1$ 到 $M$ 的边的连通无向图。该图中可能存在重边，但不存在自环。

每条边都带有一个标签，该标签是 $1$ 到 $N$ 之间的整数。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，其标签为 $c_i$。

你需要在每个顶点上写下一个 $1$ 到 $N$ 之间的整数（不同顶点可以写相同的数），然后仅保留满足以下条件的边，其余的边都要删除。

条件：设该边两端顶点上写的整数分别为 $x$ 和 $y$，则 $x$ 和 $y$ 中恰好有一个等于该边的标签。

删除不满足上述条件的边后，若图仍然连通，则称这种顶点赋值方式为好的赋值方式。请判断是否存在好的赋值方式，若存在，请给出一个例子。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$u_1$ $v_1$ $c_1$
$\vdots$
$u_M$ $v_M$ $c_M$

输出格式

如果不存在好的赋值方式，输出 No。
如果存在，输出 $N$ 行，第 $i$ 行输出顶点 $i$ 上写的整数。只要是好的赋值方式即可。

样例 1

输入

3 4
1 2 1
2 3 2
3 1 3
1 3 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$ 连接顶点 $1,2$，标签为 $1$。
• 只有顶点 $1$ 上的数等于标签 $1$，所以边 $1$ 保留。
• 边 $2$ 连接顶点 $2,3$，标签为 $2$。
• 只有顶点 $2$ 上的数等于标签 $2$，所以边 $2$ 保留。
• 边 $3$ 连接顶点 $1,3$，标签为 $3$。
• 两端顶点上的数都不等于标签 $3$，所以边 $3$ 被删除。
• 边 $4$ 连接顶点 $1,3$，标签为 $1$。
• 两端顶点上的数都等于标签 $1$，所以边 $4$ 被删除。
• 删除边 $3,4$ 后，图仍然连通，因此该赋值方式是好的赋值方式。

由 ChatGPT 4.1 翻译