Problem: We have a tree with N vertices numbered 1 to N. The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i. Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:

* For any two vertices painted in the same color, the distance between them is an even number.



Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

Constraints

* All values in input are integers.
* 1 \leq N \leq 10^5
* 1 \leq u_i < v_i \leq N
* 1 \leq w_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N
u_1 v_1 w_1
u_2 v_2 w_2
.
.
.
u_{N - 1} v_{N - 1} w_{N - 1}


Output

Print a coloring of the vertices that satisfies the condition, in N lines. The i-th line should contain `0` if Vertex i is painted white and `1` if it is painted black.

If there are multiple colorings that satisfy the condition, any of them will be accepted.

Examples

Input

3
1 2 2
2 3 1


Output

0
0
1


Input

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


Output

1
0
1
0
1

Solution (in JAVA):

Solution:
import java.util.*;
public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		D(sc);
	}
	
	public static void A(Scanner sc) {
		int n = sc.nextInt();
		int k = sc.nextInt()-1;
		String s = sc.next();
		System.out.println(s.substring(0,k)+Character.toLowerCase(s.charAt(k))+s.substring(k+1,n));
	}
	
	public static void B(Scanner sc) {
		String s = sc.next();
		if((Integer.valueOf(s.substring(0,2))==0 || Integer.valueOf(s.substring(0,2))>=13) && Integer.valueOf(s.substring(2,4))<=12 && Integer.valueOf(s.substring(2,4))>=1) System.out.println("YYMM");
		else if((Integer.valueOf(s.substring(2,4))>=13 ||Integer.valueOf(s.substring(2,4))==0)&& Integer.valueOf(s.substring(0,2))<=12 && Integer.valueOf(s.substring(0,2))>=1) System.out.println("MMYY");
		else if(Integer.valueOf(s.substring(2,4))<=12 && Integer.valueOf(s.substring(0,2))<=12 && Integer.valueOf(s.substring(2,4))>=1 && Integer.valueOf(s.substring(0,2))>=1) System.out.println("AMBIGUOUS");
		else System.out.println("NA");
	}
	
	public static int findminl(int x, int k) {
		int ret = 1;
		int pro = x*2;
		while(pro<k) {
			ret++;
			pro*=2;
		}
		return ret;
	}
	
	public static void C(Scanner sc) {
		int n = sc.nextInt();
		int k = sc.nextInt();
		double ret = (n>=k)? (n-k+1)/(double)n:0.0;
		for(int i=1;i<=Math.min(k-1,n);i++) ret+=((1.0/Math.pow(2.0, findminl(i,k)))*(1.0/n));
		System.out.println(ret);
	}
	
	public static void colin(int root, ArrayList<ArrayList<int[]>> edge,  int[] col, boolean even) {
		if(col[root]!=0) return;
		if(even) col[root]=1;
		else col[root]=-1;
		for(int[] nw :edge.get(root)) {
			boolean ev;
			if(nw[1]%2==0) ev = even;
			else ev = !even;
			colin(nw[0],edge,col,ev);
		}
	}
	
	public static void D(Scanner sc) {
		int n = sc.nextInt();
		int[] col = new int[n+1];
		col[0] = 2;
		ArrayList<ArrayList<int[]>> edge = new ArrayList<ArrayList<int[]>>();
		for(int i=0;i<=n;i++) {
			edge.add(new ArrayList<int[]>());
		}
		for(int i=1;i<=n-1;i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			edge.get(u).add(new int[] {v,w});
			edge.get(v).add(new int[] {u,w});
		}
		for(int i=1;i<=n;i++) {
			if(col[i]==0) colin(i,edge,col,true);
		}
		for(int i=1;i<=n;i++) {
			if(col[i]==1) System.out.println(1);
			else System.out.println(0);
		}
	}
}