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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author Silviase
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    Scanner in = new Scanner(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    ABC126DEvenRelation solver = new ABC126DEvenRelation();
    solver.solve(1, in, out);
    out.close();
  }

  static class ABC126DEvenRelation {

    public void solve(int testNumber, Scanner in, PrintWriter out) {
      PotentialUnionFind puf = new PotentialUnionFind();
      StringBuilder sb = new StringBuilder();
      int n = in.nextInt();
      int[] u = new int[n];
      int[] v = new int[n];
      long[] w = new long[n];
      puf.init(n);
      for (int i = 0; i < n - 1; i++) {
        u[i] = in.nextInt() - 1;
        v[i] = in.nextInt() - 1;
        w[i] = in.nextLong();
        puf.union(u[i], v[i], w[i]);
      }

      for (int i = 0; i < n; i++) {
        sb.append(((puf.potential(i) % 2)+2)%2);
        sb.append("\n");
      }
      out.println(new String(sb));

    }

  }

  static class UnionFind {

    int[] par;
    int[] rank;

  }

  static class PotentialUnionFind extends UnionFind {

    private long[] pot;

    void init(int n) {
      par = new int[n];
      rank = new int[n];
      pot = new long[n];
      for (int i = 0; i < n; i++) {
        par[i] = i; // はじめは全員が根である
        rank[i] = 0;
        pot[i] = 0;
      }
    }

    int root(int x) {
      if (par[x] == x) {
        return x;
      } else {
        int r = root(par[x]);
        pot[x] += pot[par[x]];
        par[x] = r;
        return par[x];
      }
    }

    void union(int x, int y, long w) {
      w = w + potential(x) - potential(y);
      int rx = root(x);
      int ry = root(y);
      if (rx == ry) {
        return;
      }
      if (rank[rx] < rank[ry]) {
        int tmp = rx;
        rx = ry;
        ry = tmp;
        w = -w;
      }
      if (rank[rx] == rank[ry]) {
        rank[rx]++;
      }
      par[ry] = rx;
      pot[ry] = w;
    }

    long potential(int x) {
      root(x);
      return pot[x];
    }

  }
}