题目描述

$1$ から $N$ の番号がついた $N$ 個の頂点と $1$ から $M$ の番号がついた $M$ 本の辺からなる連結な無向グラフが与えられます。 このグラフに多重辺は存在するかもしれませんが、自己ループはありません。

このグラフのそれぞれの辺には $1$ 以上 $N$ 以下の整数で表されるラベルがついています。 辺 $i$ はラベル $c_i$ がついており、頂点 $u_i,v_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$ に書き込む整数を出力せよ。 この書き込み方がよい書き込み方ならば正解となる。

题目大意

给定一个 $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。

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$
• 与えられるグラフは連結
• 与えられるグラフに自己ループはない

Sample Explanation 1

- 頂点 $1,2,3$ にそれぞれ $1,2,1$ を書き込みます。 - 辺 $1$ は頂点 $1,2$ をつないでおり、ラベルが $1$ です。 - 頂点 $1$ に書き込まれた整数のみが辺についたラベルと等しいため辺 $1$ は取り除かれません。 - 辺 $2$ は頂点 $2,3$ をつないでおり、ラベルが $2$ です。 - 頂点 $2$ に書き込まれた整数のみが辺についたラベルと等しいため辺 $2$ は取り除かれません。 - 辺 $3$ は頂点 $1,3$ をつないでおり、ラベルが $3$ です。 - どちらの頂点に書き込まれた整数も辺についたラベルと異なるため辺 $3$ は取り除かれます。 - 辺 $4$ は頂点 $1,3$ をつないでおり、ラベルが $1$ です。 - どちらの頂点に書き込まれた整数も辺についたラベルと等しいため辺 $4$ は取り除かれます。 - 辺 $3,4$ が取り除かれたあともグラフは連結なので、この書き込み方はよい書き込み方です。