题目描述

一棵树有 N 个节点，编号为 1 至 N。树的第 i 条边连接节点 u i 和节点 v i ，长度为 w i 。你应将这棵树的所有节点染上黑色或白色（所有节点可以是同一种颜色），染色后的树应满足：对于任意两个相同颜色的节点，它们之间的距离是偶数。

输出字典序最小的一组合法的解，第 i 行输出 i 号节点的颜色。输出 0 表示该节点是白色，输出 1 表示该节点为黑色。可以证明该问题至少有一组解。

保证所有输入都是整数。

输入

第一行一个整数 N。

接下来 N − 1 行，每行三个整数 u i , v i , w i 。

输出

按节点编号输出染色后的节点颜色，若有多组解，输出字典序最小的一个。

样例1

3
1 2 2
2 3 1

输出

0
0
1

样例2

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

输出

0
0
0
0
0

数据范围

对于 15% 的数据， 1≤N≤10。

对于另外 15% 的数据， w i 全为奇数，或全为偶数。

对于 100% 的数据， 1≤N≤1e5 ， 1 ≤ u i < v i ≤ N, 1 ≤ w i ≤ 1e9 。