配点 : $400$ 点

問題文

$N$ 頂点の木があります。 この木の $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでおり、その長さは $w_i$ です。 あなたは以下の条件を満たすように、この木の頂点を白と黒の $2$ 色で塗り分けたいです (すべての頂点を同じ色で塗っても構いません)。

• 同じ色に塗られた任意の $2$ 頂点について、その距離が偶数である。

条件を満たす塗り分け方を $1$ つ見つけて出力してください。この問題の制約下では、そのような塗り分け方が必ず $1$ つは存在することが証明できます。

制約

• 入力は全て整数である。
• $1 \leq N \leq 10^5$
• $1 \leq u_i < v_i \leq N$
• $1 \leq w_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$u_1$ $v_1$ $w_1$

$u_2$ $v_2$ $w_2$

$.$

$.$

$.$

$u_{N - 1}$ $v_{N - 1}$ $w_{N - 1}$

出力

題意の条件を満たすような頂点の塗り分け方を $N$ 行に分けて出力せよ。 $i$ 行目には、頂点 $i$ を白く塗る場合は 0 を、黒く塗る場合は 1 を出力せよ。

条件を満たす塗り分け方が複数存在する場合、どれを出力してもよい。

3
1 2 2
2 3 1

0
0
1

5
2 5 2
2 3 10
1 3 8
3 4 2

1
0
1
0
1