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.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.NoSuchElementException;

public class Main {
    private static FastScanner sc = new FastScanner();
    static Node[] V;
    static ArrayDeque<Stack> stk = new ArrayDeque<>();

    public static void main(String[] args) {
    	int n = sc.nextInt();
    	V = new Node[n];
    	for(int i=0; i<n; i++) {
    		V[i] = new Node();
    	}
    	for(int i=0; i<n-1; i++) {
    		int a = sc.nextInt() - 1;
    		int b = sc.nextInt() - 1;
    		int w = sc.nextInt();
    		if(w%2 == 0) {
    			V[a].evennbr.add(b);
        		V[b].evennbr.add(a);
    		} else {
    			V[a].oddnbr.add(b);
        		V[b].oddnbr.add(a);
    		}
    	}
    	V[0].dfs(false);
    	for(int i=0; i<n; i++) {
    		if(V[i].color) {
    			System.out.println(0);
    		} else {
    			System.out.println(1);
    		}
    	}
    }

    static class Node {
        HashSet<Integer> oddnbr = new HashSet<>();
        HashSet<Integer> evennbr = new HashSet<>();
        boolean vst = false;
        boolean color;
        void dfs(boolean mode) {
        	vst = true;
        	color = mode;
        	for(int x : oddnbr) {
        		if(!V[x].vst) {
        			V[x].dfs(!mode);
        		}
        	}
        	for(int x : evennbr) {
        		if(!V[x].vst) {
        			V[x].dfs(mode);
        		}
        	}
        }
    }

    static class Stack {
    	int idx;
		Stack(int idx) {
			this.idx = idx;
		}

    }

    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}