题目描述

给定一个无向连通图，有 $N$ 个顶点从 $1$ 到 $N$ 编号和 $M$ 条边从 $1$ 到 $M$ 编号。给定图中可能包含多重边但没有自环。

每条边都有一个整数标签，范围在 $1$ 到 $N$ 之间（包含边界值）。边 $i$ 有标签 $c_i$，它双向连接顶点 $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$ 行应包含写在顶点 $i$ 上的整数。任何一种“好”的整数写法都将被接受。

示例输入 1

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

示例输出 1

1
2
1

• 我们在顶点 $1$、$2$ 和 $3$ 上分别写了 $1$、$2$ 和 $1$。
• 边 $1$ 连接顶点 $1$ 和 $2$，其标签为 $1$。
  • 仅顶点 $1$ 上写的整数等于标签，因此这条边不会被移除。
• 边 $2$ 连接顶点 $2$ 和 $3$，其标签为 $2$。
  • 仅顶点 $2$ 上写的整数等于标签，因此这条边不会被移除。
• 边 $3$ 连接顶点 $1$ 和 $3$，其标签为 $3$。
  • 顶点上写的整数与标签都不相等，因此这条边将被移除。
• 边 $4$ 连接顶点 $1$ 和 $3$，其标签为 $1$。
  • 顶点上写的整数与标签都相等，因此这条边将被移除。
• 移除边 $3$ 和 $4$ 后，图仍然连通，因此这是一种“好”的整数写法。