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

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  private static class Pair {
    int u;
    int v;
    long w;
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */
    int n = sc.nextInt();

    // u1 is always in white
    Set<Integer> white = new HashSet<>();

    Set<Integer> black = new HashSet<>();

    // u -> [(u, v, w), .. ]
    Map<Integer, List<Pair>> rslvs = new HashMap<>();

    for (int i = 0; i < n - 1; i++) {
      int u = sc.nextInt();
      int v = sc.nextInt();
      long w = sc.nextLong();

      List<Pair> list1 = rslvs.getOrDefault(u, new ArrayList<>());
      Pair p1 = new Pair();
      p1.u = u;
      p1.v = v;
      p1.w = w;
      list1.add(p1);
      rslvs.put(u, list1);

      List<Pair> list2 = rslvs.getOrDefault(v, new ArrayList<>());
      Pair p2 = new Pair();
      p2.u = v;
      p2.v = u;
      p2.w = w;
      list2.add(p2);
      rslvs.put(v, list2);
    }

    // 1 is always white.
    white.add(1);

    Queue<Integer> resolved = new LinkedList<>();
    resolved.add(1);
    while(!resolved.isEmpty()) {
      Integer r = resolved.remove();

      List<Pair> list = rslvs.get(r);

      for (Pair p : list) {
        // already visited
        if (white.contains(p.v) || black.contains(p.v)) {
          continue;
        }
        // u is white
        if (white.contains(p.u)) {
          if (p.w % 2 == 0) {
            white.add(p.v);
          } else {
            black.add(p.v);
          }
        } else { // u is black
          if (p.w % 2 == 0) {
            black.add(p.v);
          } else {
            white.add(p.v);
          }
        }
        resolved.add(p.v);
      }
    }

    for (int i = 1; i <= n; i++) {
      if (white.contains(i)) {
        os.println('0');
      } else {
        os.println('1');
      }
    }
  }
}