题目描述

我们有一个由$N$个顶点组成的树，顶点编号从$1$到$N$。

树中的第$i$条边连接顶点$u_i$和顶点$v_i$，边的长度为$w_i$。 我们的目标是将树中的每个顶点都涂成白色或黑色(可以将所有顶点涂成相同的颜色)，使得满足以下条件:

对于任意两个以相同颜色涂色的顶点，它们之间的距离是一个偶数。

找到满足条件的顶点涂色方案并输出。在这个问题的约束条件下，至少存在一个满足条件的涂色方案。

输入

第一行一个整数$N$,表示顶点的数目

接下来一共$N-1$条边，表示顶点$u$到$v$有一条边权为$w$的边

输出

输出一个满足条件的顶点涂色方案，共 $N$行。

第$i$行应该包含0表示顶点$i$涂成白色，1表示顶点$i$涂成黑色。

如果存在满足条件的多个涂色方案，任何一个都将被接受。

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 \leq N \leq 10^5$

$1 \leq u_i < v_i \leq N$

$1 \leq w_i \leq 10^9$