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.*;
import java.util.*;

public class Main {

	static class FastReader { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
	public static List<Pair>[] edges;
	public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		edges = new ArrayList[n+1];
		for(int i=0;i<=n;++i) edges[i] = new ArrayList<>();
		for(int i=1;i<n;++i) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			edges[u].add(new Pair(v,w));
			edges[v].add(new Pair(u,w));
		}
		int[] col = new int[n+1];
		bfs(1,0,col);
		for(int i=1;i<=n;++i) {
			out.println(col[i]);
		}
		
        out.close();
		
	}
	
	private static void bfs(int i, int j, int[] col) {
		Queue<Integer> q = new ArrayDeque<>();
		q.add(1);
		boolean[] vis = new boolean[col.length];
		vis[1] = true;
		while(q.size() > 0) {
			int node = q.poll();
			for(Pair child : edges[node]) {
				if(!vis[child.v]) {
					q.add(child.v);
					if((child.w&1) == 0)
					col[child.v] = col[node];
					else col[child.v] = col[node]^1;
					vis[child.v] = true;
				}
			}
		}
		
		
	}

	static class Pair{
		int v;
		int w;
		Pair(int v,int w){
			this.v = v;
			this.w = w;
		}
	}
}