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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Rer.init(System.in);
		int N=Rer.nextInt();
		
		wgraph wg=new wgraph(N); 
		
		for(int x=0;x<N-1;x++) {
			int u=Rer.nextInt();
			int v=Rer.nextInt();
			int w=Rer.nextInt();
			wg.add_edge(wg, u-1, v-1, w, x);
		}
		
		int[] colour=new int[N];
		
		for(int y=0;y<N;y++) {
			colour[y]=-1;
		}
		
		wg.BFS(wg, 0, colour);
		
		for(int g=0;g<N;g++) {
			System.out.println(colour[g]);
		}
	}

}

class Ndeg {
	
	int data;
	Ndeg link;
	
	Ndeg(int d,Ndeg l){
		data=d;
		link=l;
	}
}

class qdeg {
	
	protected Ndeg front;
	protected Ndeg rear;
	int size;
	
	qdeg(){
		front=null;
		rear=null;
		size=0;
	}
	
	boolean isEmpty() {
		return rear==null;
	}
	
	void enqueue(int x) {
		Ndeg nptr=new Ndeg(x,null);
		if(rear==null) {
			front=nptr;
		}
		else {
			rear.link=nptr;
		}
		rear=nptr;
		size++;
	}
	
	int dequeue() {
		int n=front.data;
		front=front.link;
		if(front==null) {
			rear=null;
		}
		size--;
		return n; 
	}
	
	int see() {
		int n=front.data;
		return n;
	}
	
}

class edge{
	int src;
	int dest;
	long weight;
	int index;
	
	edge(int d,long w,int i){
		dest=d;
		weight=w;
		index=i;
	}
	
	edge(int s,int d,long w,int i){
		src=s;
		dest=d;
		weight=w;
		index=i;
	}
	
}	

class wgraph{
	int n;
	ArrayList<ArrayList<edge>> adj;
	
	wgraph(int V) {
		n=V;
		adj=new ArrayList<ArrayList<edge>>();
		for(int i=0;i<n;i++) {
			adj.add(new ArrayList<edge>());
		}
	}
	
	void add_edge(wgraph wg,int a,int b,int w,int i){
		edge e1=new edge(b,w,i);		// GRAPH IS UNDIRECTED
		edge e2=new edge(a,w,i);
		wg.adj.get(a).add(e1);
		wg.adj.get(b).add(e2);
	}
	
	void BFS(wgraph g,int x,int[] colour){
		/* Breadth First Search */
		/* x is the source vertex */
		
		qdeg q=new qdeg();

		q.enqueue(x);
		colour[x]=0;
		
		while(!q.isEmpty()) {
			
			int v=q.dequeue();
			ArrayList<edge> v_arr=g.adj.get(v);
			
			for(edge w : v_arr) {
				
				if(colour[w.dest]==-1) {
					if(w.weight%2==0) {
						colour[w.dest]=colour[v];
					}
					else {
						if(colour[v]==0) {
							colour[w.dest]=1;
						}
						else {
							colour[w.dest]=0;
						}
					}
					q.enqueue(w.dest);
				}
				
			}	
			
			//degree[v]=ctr;
		}
		
	}

}

/** Class for buffered reading int and double values */
class Rer {
	static BufferedReader reader;
	static StringTokenizer tokenizer;

	/** call this method to initialize reader for InputStream */
	static void init(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
	}

	/** get next word */
	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens()) {
			// TODO add check for eof if necessary
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}

	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
	
	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}
}