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.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    public static class Dijkstra {
        Vertex[] g;
        PriorityQueue<Pair> que;
        long[] d;

        public Dijkstra(int n) {
            this.g = new Vertex[n];
            this.d = new long[n];
            this.que = new PriorityQueue<>();

            for (int i = 0; i < n; i++) {
                this.g[i] = new Vertex(i);
            }
            Arrays.fill(this.d, Long.MAX_VALUE / 4);
        }

        public void set(int i, int j, long cost) {
            Vertex u = this.g[i];
            Vertex v = this.g[j];
            u.adj.add(new Edge(cost, v));
            v.adj.add(new Edge(cost, u));
        }

        public void calc(int s) {
            this.d[s] = 0;
            this.que.add(new Pair(0, this.g[s]));

            while (this.que.size() > 0) {
                Pair t = this.que.poll();
                int from = t.now.name;
                List<Edge> toes = t.now.adj;
                if (this.d[from] < t.value) {
                    continue;
                }
                for (Edge e : toes) {
                    int to = e.to.name;
                    long cost = e.w;
                    if (this.d[to] > this.d[from] + cost) {
                        this.d[to] = this.d[from] + cost;
                        this.que.add(new Pair(this.d[to], e.to));
                    }
                }
            }
        }

        public long distance(int g) {
            return this.d[g];
        }
    }

    public static class Edge {
        long w;
        Vertex to;

        public Edge(long w, Vertex to) {
            this.w = w;
            this.to = to;
        }

    }

    public static class Vertex {
        int name;
        List<Edge> adj;

        public Vertex(int name) {
            this.name = name;
            this.adj = new ArrayList<>();
        }

    }

    public static class Pair implements Comparable<Pair> {
        long value;
        Vertex now;

        public Pair(long value, Vertex now) {
            this.value = value;
            this.now = now;
        }

        @Override
        public int compareTo(Pair o) {

            return Long.compare(this.value, o.value);
        }

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        Dijkstra dijkstra = new Dijkstra(N);
        for (int i = 0; i < N - 1; i++) {
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            long w = scanner.nextLong();
            dijkstra.set(u, v, w);
        }
        dijkstra.calc(0);

        for (int i = 0; i < N; i++) {
            System.out.println(dijkstra.distance(i) % 2);
        }
    }
}