偶数距离染色

题目描述

有一棵 $N$ 个顶点的树。

这棵树的第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，长度为 $w_i$。

你想用白色和黑色两种颜色给这棵树的顶点染色，使其满足以下条件（所有顶点涂成同一种颜色也可以）。

• 对于任意 $2$ 个被涂成相同颜色的顶点，它们之间的距离为偶数。

请找出一种满足条件的染色方法并输出。可以证明，在本问题的约束下，一定存在至少一种这样的染色方法。

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

• 输入均为整数
• $1 \le N \le 10^5$
• $1 \le u_i \lt v_i \le N$
• $1 \le w_i \le 10^9$

提示

答案不唯一，输出任意合法解即可。