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.

-----Sample Input-----
3
1 2 2
2 3 1

-----Sample Output-----
0
0
1


Difficulty: interview

Starter code:

Solutions:
N = int(input())
u, v, w = [0]*(N-1), [0]*(N-1), [0]*(N-1)
n = [-1] * N
# n[][0] 色　n[][1] 連結先一覧リスト n[][2] mod2 
for i in range(N):
    n[i] = [0]*4
    n[i][1] = []
    n[i][2] = []

for i in range(N-1):
    u[i], v[i], w[i] = list(map(int, input().split()))
    n[u[i]-1][1].append(v[i]-1)
    n[v[i]-1][1].append(u[i]-1)
    n[u[i]-1][2].append(w[i]%2)
    n[v[i]-1][2].append(w[i]%2)

stack = [u[0]-1]

while True:
    num = stack.pop()
    n[num][3] = 1
    for i in range(len(n[num][1])):
        if n[n[num][1][i]][3] == 0:
            stack.append(n[num][1][i])
            if n[num][2][i] == 0:
                n[n[num][1][i]][0] = n[num][0]
            else:
                n[n[num][1][i]][0] = -1 * n[num][0] + 1
    if len(stack) == 0:
        break

for i in n:
    print(i[0])

from collections import deque

n = int(input())
tree = {i: set() for i in range(n)}
cost = {}
for _ in range(n-1):
    u, v, w = [int(x)-1 for x in input().split()]
    tree[u].add(v)
    tree[v].add(u)
    cost[(u, v)] = w + 1

color = [-1] * n
color[0] = 0
que = deque([0])
while que:
    now = que.popleft()
    for i in tree[now]:
        if color[i] != -1:
            continue
        if cost[(min(now, i), max(now, i))] % 2 == 0:
            color[i] = color[now]
        else:
            color[i] = color[now] ^ 1
        que.append(i)
print(('\n'.join(map(str, color))))


N = int(input())
Tree = [[] for _ in range(N+1)]
UVW = []

for _ in range(N-1):
  u, v, w = map(int, input().split())
  Tree[u].append(v)
  Tree[v].append(u)
  UVW.append((u, v, w))

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in Tree[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

dis = [0] * (N+1)

for u, v, w in UVW:
  if parent[u] == v:
    dis[u] = w
  else:
    dis[v] = w

color = [-1] * (N+1)
color[root] = 0

for x in order:
  for y in Tree[x]:
    if y == parent[x]:
      continue
    if dis[y]%2 == 0:
      color[y] = color[x]
    else:
      color[y] = color[x] ^ 1

for i in range(1, N+1):
  print(color[i])

n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
ls = []
for i in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))

ans = [-1] * n

exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        list = next[a]
        if a not in explored:
            next_que.append(a)
        explored.add(a)


print(*ans, end='\n')

import sys
sys.setrecursionlimit(10**8)
N = int(input())
graph = [[] for _ in range(N)]

for i in range(1, N):
    u, v, w = list(map(int, input().split()))
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))

color = [0 for _ in range(N)]
visited = [False for _ in range(N)]

def dfs(now):

    for adj in graph[now]:
        v, dist = adj
        if visited[v]:
            continue
        visited[v] = True
        color[v] = color[now] + dist
        dfs(v)

    return


for start in range(N):
    if not visited[start]:
        color[start] = 0
        visited[start] = True
        dfs(start)

for i in range(N):
    print((color[i] % 2))


N = int(input())
e = [[] for _ in range(N)]
for _ in range(N-1):
  u,v,w = map(int, input().split())
  u -= 1
  v -= 1
  e[u].append((v,w))
  e[v].append((u,w))

res = [-1]*N
res[0] = 0
q = [0]
while len(q):
  v = q.pop()
  for u,w in e[v]:
    if res[u]>=0:
      continue
    res[u] = res[v]+w
    q.append(u)

for r in res:
  print(r%2)

import sys
sys.setrecursionlimit(500*500)
n = int(input())
a = [[] for _ in range(n)]; b = [-1]*n; b[0] = 0
for i in range(n-1):
    u, v, w = map(int, input().split())
    a[u-1].append([v-1, w]); a[v-1].append([u-1, w])
def dfs(A, k):
    for i in A[k]:
        if b[i[0]] == -1:
            b[i[0]] = b[k]+i[1]
            dfs(A, i[0])
dfs(a, 0)
for i in b:
    print(0) if i%2 == 0 else print(1)

n=int(input())
col=[-1]*n
e=[[[],[]]for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    w%=2
    e[u][w].append(v)
    e[v][w].append(u)
col[0]=1
from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
dq.append(0)
while dq:
    a=dq.pop()
    b=col[a]
    for i in range(2):
        for ne in e[a][i]:
            if col[ne]==-1:
                col[ne]=b^i
                dq.appendleft(ne)
print(*col,sep='\n')

from collections import deque

N = int(input())

graph = [[] for _ in range(N+1)]
cost = [[] for _ in range(N+1)]
ans = [-1] * (N+1)

for query in range(N-1):
    u, v, w = map(int, input().split())
    graph[u].append(v)
    cost[u].append(w % 2)
    graph[v].append(u)
    cost[v].append(w % 2)
#print('input')

que = deque()

ans[1] = 0
que.append(1)

while que:
    now = que.popleft()
    #print(graph[now])
    for index in range(len(graph[now])):
        nextg = graph[now][index]
        nextc = cost[now][index]
        #print(ans[nextg])
        if ans[nextg] != -1:
            #print('continued')
            continue
        que.append(nextg)

        #print(nextc)
        if nextc == 1:
            ans[nextg] = (ans[now] + 1) % 2
        else:
            ans[nextg] = ans[now]
    #print(que)
    #print(ans)

#print(ans)

for i in range(1, N+1):
    print(ans[i])

import sys
sys.setrecursionlimit(10**9)


N = int(input())
to = [[] for _ in range(N)]

for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    to[u].append([v, w])
    to[v].append([u, w])


def dfs(v, color):
    for nv, w in to[v]:
        if color[nv] == -1:
            if w % 2:
                color[nv] = color[v] ^ 1
            else:
                color[nv] = color[v]
            dfs(nv, color)


def main():
    color = [-1] * N
    color[0] = 0
    dfs(0, color)
    print(*color, sep='\n')


def __starting_point():
    main()
__starting_point()

n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
ls = []
for i in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))

ans = [-1] * n

exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        list = next[a]
        if a not in explored:
            next_que.append(a)
        explored.add(a)


for i in ans:
    print(i)

import sys

sys.setrecursionlimit(10**7)


def dfs(s, to, color):
    for next_v, step in to[s]:
        if color[next_v] == -1:
            if step % 2 == 0:
                color[next_v] = color[s]
            else:
                color[next_v] = color[s] ^ 1
            dfs(next_v, to, color)


def solve():
    N = int(input())
    to = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        u, v = u - 1, v - 1
        to[u].append([v, w])
        to[v].append([u, w])

    color = [-1] * N #-1: 未探索、0: 白、1: 黒
    color[0] = 0
    dfs(0, to, color)
    print(*color, sep='\n')


def __starting_point():
    solve()
__starting_point()


from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

di[0]=0

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=[[0,0]]
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        for z, dist in G[y]:
            if seen[z] == 0:
                di[z] = d + dist
                stack.append([z, d + dist])

for i in range(N):
    if di[i]%2==0:
        print(0)
    else:
        print(1)

n = int(input())
uv = [[] for _ in range(n+1)]
for i in range(n-1):
    u,v,w = map(int, input().split())
    uv[u].append([v,w])
    uv[v].append([u,w])
stack = [1]
ans = [-1]*(n+1)
ans[1]=0
while stack:
    x = stack.pop()
    for j,k in uv[x]:
        if ans[j] == -1:
            if k % 2 ==0:
                ans[j] = ans[x]
            else:
                ans[j] = (ans[x]+1)%2
            stack.append(j)
for m in range(n):
    print(ans[m+1])

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(u:int, v:int):
    cv = color[v]
    for s, k in graph[v]:
        if s == u:
            continue
        elif color[s] != -1:
            continue
        elif k%2 == 0:
            color[s] = cv
            dfs(v, s)
        else:
            color[s] = (cv+1)%2
            dfs(v, s)

def main():
    nonlocal color, graph
    N = int(input())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = list(map(int, input().split()))
        graph[u-1].append((v-1, w))
        graph[v-1].append((u-1, w))
    color = [-1] * N

    color[0] = 0
    dfs(-1, 0)

    for c in color:
        print(c)

def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10**7)
N = int(input())

Graph = [[] for _ in range(N+1)]
dist  = [1000000000000]*(N+1)

for i in range(N-1):
	u,v,w = map(int,input().split())
	u-=1
	v-=1
	Graph[u].append((v,w))
	Graph[v].append((u,w))


def func(fromE,now,length):
	dist[now] = length
	for i in range(len(Graph[now])):
		target = Graph[now][i][0]
		lengt  = Graph[now][i][1]

		if target == fromE:
			continue

		func(now,target,dist[now]+lengt)

func(-1,0,0)

for i in range(N):
	if dist[i]%2 == 0:
		print(0)
	else:
		print(1)

n = int(input())
e = [list() for _ in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    e[u-1] += [[v,w]]
    e[v-1] += [[u,w]]

visited = [-1]*n
stack = [0]
visited[0]=0
while stack:
    z = stack.pop()
    for v,w in e[z]:
        if visited[v-1]==-1:
            stack.append(v-1)
            if w%2==0:
                visited[v-1]=visited[z]
            else:
                visited[v-1]=1-visited[z]
        else:
            continue
print(*visited,sep="\n") 

from collections import deque
n = int(input())
ans = [-1] * n
ans[0] = 0
d = [[] for _ in range(n)]

for i in range(n - 1):
    u, v, w = map(int, input().split())
    d[u - 1].append([v - 1, w])
    d[v - 1].append([u - 1, w])

cnt = 0
queue = deque()
queue.append(0)
while queue:
    u = queue.pop()
    for v, w in d[u]:
        if ans[v] == -1:
            if w % 2 == 0:
                ans[v] = ans[u]
            else:
                ans[v] = ans[u] ^ 1
            queue.append(v)


for i in range(n):
    print(ans[i])

from collections import deque
import sys
sys.setrecursionlimit(10**7)
n = int(input())
ad_ls = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,w = map(int,input().split())
    ad_ls[a-1].append([b-1,w])
    ad_ls[b-1].append([a-1,w])

cost_ls = [0] * n
done_ls = [0] * n
def dfs(v,c):
    for new,cost in ad_ls[v]:
        if not done_ls[new]:
            cost_ls[new] = c+cost
            done_ls[new] = 1
            dfs(new,c+cost)

dfs(0,0)

color_ls = [0] * n
for i in range(n):
    color_ls[i] = cost_ls[i] % 2

for color in color_ls:
    print(color)

import sys
sys.setrecursionlimit(10**7)

class TreeNode:
    def __init__(self, num):
        self.num = num
        self.vertexs = [] # (ノード番号, 距離)
        self.color = None
    
    def set_color(self, color):
        self.color = color

class Tree:
    def __init__(self, N):
        self.nodes = [TreeNode(i) for i in range(N)]

    def set_vertex(self, u, v, w):
        self.nodes[u - 1].vertexs.append((v - 1, w))
        self.nodes[v - 1].vertexs.append((u - 1, w))
    
    def set_color(self):
        self.nodes[0].set_color(0)
        def set_color(node, prev_node):
            for n, w in node.vertexs:
                if n != prev_node.num:
                    continue
                if w % 2 == 0:
                    node.set_color(prev_node.color)
                else:
                    new_color = abs(prev_node.color - 1)
                    node.set_color(new_color)
        self.do_and_next(0, -1, set_color)

    def print_tree_num(self):
        for i, node in enumerate(self.nodes):
            print(i, node.vertexs, node.color)

    def print_tree_deep(self):
        print_color = lambda x, p: print(x.color)
        self.do_and_next(0, -1, print_color)

    def do_and_next(self, node_num, prev_node_num, f):
        f(self.nodes[node_num], self.nodes[prev_node_num])
        for n, w in self.nodes[node_num].vertexs:
            if n == prev_node_num:
                continue
            self.do_and_next(n, node_num, f)

    def print_color(self):
        for node in self.nodes:
            print(node.color)

N = int(input())
tree = Tree(N)
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    tree.set_vertex(u, v, w)

tree.set_color()
tree.print_color()

from collections import deque
n=int(input())
uv=[[] for _ in range(n+1)]
for i in range(n-1):
    u,v,w=list(map(int,input().split()))
    uv[u].append([v,w])
    uv[v].append([u,w])
stack=[1]
ans=[-1]*(n+1)
ans[1]=0
while stack:
    x=stack.pop()
    for j in uv[x]:
        if ans[j[0]]==-1:
            if j[1]%2==0:
                ans[j[0]]=ans[x]
            else:
                ans[j[0]]=(ans[x]+1)%2
            stack.append(j[0])

for k in range(1,n+1):
    print((ans[k]))


import collections

n = int(input())
graph = [[] for i in range(n + 1)]
flag = [False for i in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append([v, w])
    graph[v].append([u, w])
color = [None for i in range(n + 1)]
color[1] = 0
queue = collections.deque([1])
while queue:
    test = queue.popleft()
    flag[test] = True
    for i in graph[test]:
        if flag[i[0]] == True:
            continue
        queue.append(i[0])
        color[i[0]] = i[1] % 2 ^ color[test]
for i in range(n):
    print(color[i + 1])

from collections import deque
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  g[u-1].append((v-1,w))
  g[v-1].append((u-1,w))
ds = [-1]*n
dq = deque([0])
ds[0] = 0
while dq:
  t = dq.popleft()
  for i in g[t]:
    if ds[i[0]] == -1:
      ds[i[0]] = ds[t] + i[1]
      dq.append((i[0]))
for i in ds:
  if i%2 == 0:
    print((0))
  else:
    print((1))


import sys
from collections import deque

input = sys.stdin.readline


def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        u, v, w = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u].append((v, w))
        G[v].append((u, w))

    ans = [-1] * N
    ans[0] = 0
    stack = deque([(-1, 0)])
    while stack:
        p, u = stack.pop()
        for v, w in G[u]:
            if v == p:
                continue
            if w % 2 == 0:
                ans[v] = ans[u]
            else:
                ans[v] = (ans[u] + 1) % 2
            stack.append((u, v))

    print(("\n".join(map(str, ans))))


def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(20000000)


def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size) % 2)
            dfs(next_node, distance+edge_size)


N = int(input())

G = [[] for i in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    G[u-1].append([v-1, w])
    G[v-1].append([u-1, w])

ans = [-1]*N
dfs(0, 0)
print(*ans, sep='\n')

N = int(input())
ans = [-1] * N
ans[0] = 0
root = [[] for i in range(N)]
for i in range(N - 1):
  u, v, w = list(map(int, input().split()))
  root[u - 1].append([v - 1, w])
  root[v - 1].append([u - 1, w])
#print(root)

visited = [0] * N
visited[0] = 1
queue = [0]
while queue:
  x = queue.pop()
  for i, value in root[x]:
    if value % 2 == 0:
      ans[i] = ans[x]
    else:
      ans[i] = abs(1 - ans[x])
    if visited[i] == 0:
      visited[i] = 1
      queue.append(i)
      
#print(ans)      
for i in range(N):
  print((ans[i]))
              
      
      
      
      
      



import sys
sys.setrecursionlimit(10**6)
n=int(input())
path=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    path[u-1].append((v-1,w%2))
    path[v-1].append((u-1,w%2))
ans=[0]+[-1]*(n-1)
def dfs(i):
    nonlocal n,path,ans
    for j in path[i]:
        if ans[j[0]]==-1:
            if j[1]:
                ans[j[0]]=1-ans[i]
                dfs(j[0])
            else:
                ans[j[0]]=ans[i]
                dfs(j[0])
dfs(0)
print("\n".join(map(str,ans)))

from collections import deque
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))
ds = [-1]*n
dq = deque([0])
ds[0] = 0
while dq:
    t = dq.popleft()
    for i in g[t]:
        if ds[i[0]] == -1:
            ds[i[0]] = ds[t] + i[1]
            dq.append((i[0]))
for i in ds:
    if i%2 == 0:
        print(0)
    else:
        print(1)

from collections import deque

N = int(input())


vlist = [[] for _ in range(N)]

for i in range(N-1):
    a,b,w = list(map(int, input().split()))
    a -= 1
    b -= 1
    vlist[a].append((b,w))
    vlist[b].append((a,w))

ans = [-1] * N
q = deque()

ans[0] = 0
q.append(0)

while q:
    new = q.popleft()
    for node, weight in vlist[new]:
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.append(node)
    
for i in ans:
    print(i)





import sys
sys.setrecursionlimit(10**7)

N=int(input())
graph=[[] for _ in range(N)]

for _ in range(N-1):
    u,v,w=list(map(int,input().split()))
    u-=1
    v-=1
    graph[u].append([v,w])
    graph[v].append([u,w])

color=[-1]*N
def even(v=0,col=0):
    color[v]=col
    for i in range(len(graph[v])):
        nv,nw=list(map(int,graph[v][i]))
        if color[nv]!=-1: continue
        if nw%2==0:
            even(nv,col)
        else:
            even(nv,1-col)

even()
for i in range(N):
    print((color[i]))


from collections import deque
N=int(input())
visited=[-1]*N
l=[[] for i in range(N)]
for i in range(N-1):
   a,b,c=map(int,input().split())
   a-=1;b-=1
   l[a].append((b,c%2))
   l[b].append((a,c%2))
def ans(node,dis):
   visited[node]=0
   que=deque(l[node])
   while que:
      node,dis=que.popleft()
      visited[node]=dis
      for i,j in l[node]:
         if visited[i]==-1:
            visited[i]=(dis+j)%2
            que.append((i,(dis+j)%2))
ans(0,0)
for i in visited:
   print(i)

import sys
sys.setrecursionlimit(10**7)


n = int(input())
col = [0]*n
next = [[] for i in range(n)]
d = [float('INF')]*n
d[0]=0

def dfs(now,parent):
    for next1,w1 in next[now]:
        if next1 == parent:
            continue
        elif d[next1]==float('INF'):
            d[next1]=d[now]+w1
            dfs(next1,now)

for i in range(n-1):
    u , v , w = list(map(int, input().split()))
    next[u-1].append((v-1,w))
    next[v-1].append((u-1,w))

dfs(0,-1)

for i in range(n):
    if d[i]%2==0:
        print('0')
    else:
        print('1')



import sys
sys.setrecursionlimit(10**9)
def dfs(i):
  if reached[i] == 1:
    return
  reached[i] = 1
  for dic in uv[i]:
    to = dic["to"]
    w = dic["weight"]
    if w % 2 == 0:
      color[to] = color[i]
    else:
      color[to] = int(not color[i])
    dfs(to)

n = int(input())
color = [0]*(n+1)
reached = [0]*(n+1)
uv = [[] * (n+1) for i in range(n+1)]
for i in range(n-1):
  u,v,w = map(int,input().split())
  uv[u].append({"to":v, "weight":w})
  uv[v].append({"to":u, "weight":w})
dfs(1)
for i in color[1:]:
  print(i)

from collections import deque

N = int(input())
ki = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    ki[u-1].append([v-1, w])
    ki[v-1].append([u-1, w])
f = [False]*N
f[0] = True
c = [0]*N

q = deque([0])
while q:
    now = q.popleft()
    for nxt, w in ki[now]:
        if f[nxt]:
            continue
        if w&1:
            c[nxt] = c[now]^1
        else:
            c[nxt] = c[now]
        q.append(nxt)
        f[nxt] = True


for a in c:
    print(a)

n = int(input())

g = [[] for _ in range(n)]

for _ in range(n-1):
    u,v,w = map(int,input().split())
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))

from collections import deque

que = deque()
seen = [0] + [-1]*(n-1)
que.append(0)
while que:
    s = que.popleft()
    for v,w in g[s]:
        if seen[v] != -1:continue
        seen[v] = seen[s]^(w%2)
        que.append(v)
for i in seen:
    print(i)

def main():
    n = int(input())
    ki = {}
    for i in range(1,n+1):
        ki[i] = []
    for i in range(n-1):
        u,v,w = list(map(int,input().split()))
        ki[u] += [[v,w%2]]
        ki[v] += [[u,w%2]]
    cl = [-1 for i in range(n)]
    cl[0] = 0
    que = [0]
    while len(que)>0:
        q = que.pop(0)
        for v in ki[q+1]:
            if cl[v[0]-1] != -1:
                continue
            if v[1]==1:
                cl[v[0]-1] = (cl[q]+1)%2
                que.append(v[0]-1)
            else:
                cl[v[0]-1] = cl[q]
                que.append(v[0]-1)
    for i in range(n):
        print((cl[i]))

def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(500*500)


n = int(input())
nodes = [list(map(int,input().split())) for _ in range(n-1)]
a = [[] for _ in range(n+1)]

for node in nodes:
    a[node[0]].append([node[1],node[2]])
    a[node[1]].append([node[0],node[2]])

depth = [-1] * (n+1)
depth[1] = 0

def dfs(a,s):
    for v in a[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(a,v[0])    
dfs(a,1)
for d in depth[1:]:
    if d % 2 == 0:
        print((0))
    else:
        print((1))


import sys
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, sys.stdin.readline().split())
    u -= 1
    v -= 1
    G[u].append((v, w))
    G[v].append((u, w))

done = {}
todo = [(0, 0, 0)]
while todo:
    i, c, d = todo.pop()
    for ni, dd in G[i]:
        if ni in done:
            continue
        nd = d + dd
        nc = nd % 2
        todo.append((ni, nc, nd))
    done[i] = c

for i in range(N):
    print(done[i])

n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
for i in range(n-1):
    u, v, w= map(int, input().split())
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))
ans = [-1] * n
exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        if a not in explored:
            next_que.append(a)
        explored.add(a)

print(*ans, end='\n')

from collections import deque

n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]

l = [[] for _ in range(n)]
for u, v, w in uvw:
    u, v = u-1, v-1
    l[u].append((v, w))
    l[v].append((u, w))

ans = [0] * n
parents = [-1] * n
q = deque([0])
while q:
    a = q.pop()
    for i, j in l[a]:
        if i == parents[a]:
            continue
        parents[i] = a
        q.append(i)
        ans[i] = ans[a] if j%2 == 0 else (ans[a]+1) % 2
for i in ans:
    print(i)

n = int(input())
d = [[] for i in range(n)]
for i in range(n-1):
  u, v, w = map(int, input().split())
  d[u-1].append([v-1, w])
  d[v-1].append([u-1, w])
  
ans = [[] for i in range(n)]
ans[0].append(0)
q = [0]

while q:
  x = q.pop()
  for u, w in d[x]:
    if not ans[u]:
      buf = ans[x][0]
      if w%2==1:
        buf = (buf+1)%2
      ans[u].append(buf)
      q.append(u)
    
for i in ans:
  print(*i)

#!/usr/bin/env python
# coding: utf-8

# In[3]:


from collections import deque


# In[4]:


N = int(input())
g = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = list(map(int, input().split()))
    g[u-1].append([v-1,w])
    g[v-1].append([u-1,w])


# In[5]:


que = deque()
seen = [0]+[-1]*(N-1)
que.append(0)
while que:
    s = que.popleft()
    for v,w in g[s]:
        if seen[v] != -1:
            continue
        seen[v] = seen[s]^(w%2)
        que.append(v)
for i in seen:
    print(i)


# In[ ]:






from sys import setrecursionlimit
setrecursionlimit(10 ** 7)
n = int(input())
uvw = [list(map(int, input().split())) for i in range(n - 1)]
d = [-1 for i in range(n)]
edge = [[] for i in range(n)]
for u, v, w in uvw:
    edge[u - 1].append((v - 1, w))
    edge[v - 1].append((u - 1, w))
def dfs(now, D):
    d[now] = D
    for i, j in edge[now]:
        if d[i] == -1:
            dfs(i, D + j)
dfs(0, 0)
for i in d:
    print(i % 2)

from collections import deque

def bfs(s):
    nonlocal color
    q = deque()
    q.append(s)
    color[s] = 0
    while q:
        i = q.popleft()
        for g in G[i]:
            if color[g[0]] == -1:
                if g[1] % 2 == 0:
                    color[g[0]] = color[i]
                else:
                    color[g[0]] = 1 - color[i]
                q.append(g[0])
    return

n = int(input())
G = [[] for _ in range(n + 1)]
color = [-1] * (n + 1)
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    G[u].append([v, w])
    G[v].append([u, w])
bfs(1)
for i in range(1, n + 1):
    print(color[i])

from collections import deque
n = int(input())
ad_ls = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,w = list(map(int,input().split()))
    ad_ls[a-1].append([b-1,w])
    ad_ls[b-1].append([a-1,w])

cost_ls = [0] * n
done_ls = [0] * n
done_ls[0] = 1
q = deque()
q.append(0)

while q:
    now = q.pop()
    for new in ad_ls[now]:
        nex,cost = new[0],new[1]
        if not done_ls[nex]:
            cost_ls[nex] = cost + cost_ls[now]
            done_ls[nex] = 1
            q.append(nex)

color_ls = [0] * n
for i in range(n):
    color_ls[i] = cost_ls[i] % 2

for color in color_ls:
    print(color)



n=int(input())
L=[[] for i in range(n+1)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    L[u].append((v,w%2))
    L[v].append((u,w%2))

V=[0 for i in range(n+1)]
V[1]=1
ans=[0 for i in range(n+1)]
que=[1]
head=0

while len(que)>head:
    now=que[head]
    head+=1
    for nex in L[now]:
        if V[nex[0]]==0:
            V[nex[0]]=1
            ans[nex[0]]=ans[now]^nex[1]
            que.append(nex[0])
    
for pri in ans[1:]:
    print(pri)

import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        u, v, w = mi()
        u -= 1
        v -= 1
        edge[u].append((v, w))
        edge[v].append((u, w))
    dist = [0]*n
    parent = [-1]*n
    que = deque([0])
    while que:
        v = que.pop()
        for nv, nx in edge[v]:
            if parent[v] == nv:
                continue
            parent[nv] = v
            dist[nv] = dist[v]+nx%2
            dist[nv]%= 2
            que.append(nv)
    print(*dist, sep='\n')
    


def __starting_point():
    main()
__starting_point()

# D - Even Relation
from typing import List, Tuple


def main():
    N, *X = list(map(int, open(0).read().split()))
    tree: List[List[Tuple[int, int]]] = [[] for _ in range(N + 1)]
    for u, v, w in zip(*[iter(X)] * 3):
        w %= 2
        tree[u].append((v, w)), tree[v].append((u, w))

    color = [-1] * (N + 1)
    color[1] = 1
    stack = [1]
    while stack:
        u = stack.pop()
        cur = color[u]
        for v, w in tree[u]:
            if color[v] != -1:
                continue
            color[v] = cur ^ w
            stack.append(v)

    print(("\n".join(map(str, color[1:]))))


def __starting_point():
    main()

__starting_point()

N = int(input())
G = [[] for n in range(N+1)]
q = [(1,0)]
ans = N*[-1]

for n in range(N-1):
  u,v,w = map(int,input().split())
  G[u]+=[(v,w)]
  G[v]+=[(u,w)]

while q:
  x,y = q.pop()
  ans[x-1] = y%2 
  for g,d in G[x]:
    q+=[(g,y+d)]*(ans[g-1]<0)

print(*ans,sep="\n")

N = int(input())
dist_from_1 = [0 for i in range(N+1)]

paths = [dict() for i in range(N+1)]
for i in range(N-1):
    a, b, dist = list(map(int, input().split()))
    paths[a][b] = dist
    paths[b][a] = dist

queue = [(0, 1, 0)]
while len(queue) != 0:
    prev, now, dist = queue.pop()
    dist_from_1[now] = dist
    for next in paths[now]:
        if next == prev:
            continue
        queue.append((now, next, dist + paths[now][next]))

for i in range(1, N+1):
    if dist_from_1[i] % 2 == 0:
        print((0))
    else:
        print((1))


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())


def dfs(s, p):
    nonlocal ans
    for t, w in g[s]:
        if t == p or ans[t] >= 0:
            continue
        ans[t] = ans[s] ^ (w % 2)
        dfs(t, s)


g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append((v, w))
    g[v].append((u, w))

ans = [-1] * n
ans[0] = 0
dfs(0, -1)
print(*ans, sep="\n")


import sys
sys.setrecursionlimit(500*500)
n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]
g = [[] for _ in range(n)]

for i in l:
    v = i[0]-1
    y = i[1]-1
    w = i[2]
    g[v].append([y,w])
    g[y].append([v,w])

seen = [0] + [-1] * (n-1)

def dfs(s):
    for k in g[s]:
        v,w = k[0],k[1]
        if seen[v]!=-1:continue
        seen[v] = seen[s]^(w%2)
        dfs(v)
        
dfs(0)

for i in seen:
    print(i)

import sys,math,collections,itertools
input = sys.stdin.readline
#ダイクストラで頂点1と偶数距離を0として塗る
N=int(input())
road=[[] for i in range(N+1)]
for _ in range(N-1):
    u,v,w=list(map(int,input().split()))
    road[u].append((v,w))
    road[v].append((u,w))
dist = [float('inf')for i in range(N+1)]
ans = [0]*(N+1)

q = collections.deque([])
q.append(1)
dist[1]=0
while q:
    now = q.popleft()
    for goto,cost in road[now]:
        if dist[goto]>dist[now]+cost:
            dist[goto]=dist[now]+cost
            q.append(goto)

for a in dist[1:]:
    print((a%2))


# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)
#二部グラフになっている時の色の塗り分けを聞いている
n=int(input())
es=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=list(map(int,input().split()))
  es[u-1].append([v,w])
  es[v-1].append([u,w])

colors=[0 for i in range(n)]
#深さ優先探索　頂点vをcolorで塗ることを考える
def dfs(v,color):
  colors[v-1]=color
  for i in es[v-1]:
    if i[1]%2==0 and colors[i[0]-1]==0:
      dfs(i[0],color)
    elif i[1]%2==1 and colors[i[0]-1]==0:
      dfs(i[0],(-1)*color)
  return colors

    
a=dfs(1,-1)
for i in a:
  if i==-1:
    print((0))
  else:
    print((1))
  


from collections import deque

n = int(input())

g = [[] for _ in range(n)]
# 0indexに直している
for i in range(n - 1):
    u, v, w = list(map(int, input().split()))
    g[u - 1].append((v - 1, w))
    g[v - 1].append((u - 1, w))

"""
ex.
3
1 2 2
2 3 1
の場合、g = [[(1, 2)], [(0, 2), (2, 1)], [(1, 1)]]
"""

#print(g)

"""
根から各頂点への距離をd_iとする
u,vという2頂点について、その最小共通祖先をwとすると
uとvの距離=d_u+d_v-2d_w
第3項は常に偶数
d_uとd_vの偶奇が等しければ全体は偶数、偶奇が異なれば全体は奇数
例えば、d_iが偶数なら白に、奇数なら黒に塗るとすれば条件を満たす
"""

dq = deque([0])
#  各頂点について、根からの距離
# 頂点0を根とする（別にどれを選んでも良い）
ds = [-1] * n
ds[0] = 0

# BFS(幅優先探索)
while dq:
    t = dq.popleft()
    # tと繋がっている各頂点について
    for i in g[t]:
        # まだ調べていない場合
        if ds[i[0]] == -1:
            # 根からtまでの距離+tから次への距離
            ds[i[0]] = ds[t] + i[1]
            # 今調べた頂点をdequeに追加
            dq.append((i[0]))

# 偶数なら白、奇数なら黒とした。逆でも良い。
for i in ds:
    if i % 2 == 0:
        print((0))
    else:
        print((1))


import sys
sys.setrecursionlimit(10**9)


N = int(input())
to = [[] for _ in range(N)]

for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    to[u].append([v, w])
    to[v].append([u, w])


def dfs(v, color):
    for nv, w in to[v]:
        if color[nv] == -1:
            color[nv] = color[v] ^ (w % 2)
            dfs(nv, color)


def main():
    color = [-1] * N
    color[0] = 0
    dfs(0, color)
    print(*color, sep='\n')


def __starting_point():
    main()
__starting_point()

# coding: utf-8
import sys
import copy

sys.setrecursionlimit(10 ** 9)


def dfs(seen, graph, i):
    for v, w in graph[i]: 
        if seen[v-1] != -1:
            continue
        seen[v-1] = abs((w % 2) - seen[i])
        dfs(seen, graph, v-1)
    

def main():
    n = int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        ui, vi, wi = map(int, input().split())
        graph[ui-1].append((vi, wi))
        graph[vi-1].append((ui, wi))
    
    seen = [-1 for _ in range(n)]
    seen[0] = 0
    for i in range(n-1):
        dfs(seen, graph, i)
        
    print(*seen, sep='\n')
        
main()


import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]

for i in range(N - 1):
  u,v,w = map(int,readline().split())
  G[u - 1].append((v - 1, w))
  G[v - 1].append((u - 1, w))
  
color = [-1] * N
stack = []
stack.append([0, -1, 0])
while stack:
  v,parent,cost = stack.pop()
  color[v] = cost
  for child in G[v]:
    if child[0] == parent:
      continue
    stack.append([child[0], v, (cost + child[1]) % 2])

for c in color:
  print(c)

# import itertools
# import math
import sys
sys.setrecursionlimit(500*500)
# import numpy as np

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# H, W, K = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# S = input()

# d = sorted(d, reverse=True, key=lambda x:x[0])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

edges = [list(map(int,input().split())) for _ in range(N-1)]
tree = [[] for _ in range(N + 1)]

for edge in edges:
    tree[edge[0]].append([edge[1], edge[2]])
    tree[edge[1]].append([edge[0], edge[2]])

# print(tree)

depth = [-1] * (N + 1)
depth[1] = 0

def dfs(tree, s):
    for l in tree[s]:
        if depth[l[0]] == -1:
            depth[l[0]] = depth[s] + l[1]
            dfs(tree, l[0])

dfs(tree, 1)

# print(depth)

for l in depth[1:]:
    if l % 2 == 0:
        print((1))
    else:
        print((0))


import sys
sys.setrecursionlimit(10**5)

def f(x):
  for tmp in links[x]:
    if c[tmp[0]]<0:
      if tmp[1]%2==0:
        c[tmp[0]]=c[x]+0
      else:
        c[tmp[0]]=1-c[x]
      f(tmp[0])

N=int(input())
links=[[] for _ in range(N+1)]
for _ in range(N-1):
  u, v, w=map(int, input().split())
  links[u].append([v, w])
  links[v].append([u, w])
  
c=[-1]*(N+1)
c[1]=0
f(1)

print(*c[1:], sep='\n')

#coding: utf-8
from collections import defaultdict, deque

N = int(input())
G = {}
for i in range(1, N+1):
    G[i] = []

for i in range(N-1):
    u, v, w = (int(n) for n in input().split())
    G[u].append((v, w))
    G[v].append((u, w))

ret = [-1] * (N+1)

que = deque()
que.append((1, 0))

while len(que) > 0:
    node, distance = que[0]
    que.popleft()

    ret[node] = distance % 2
    for next_node, next_distance in G[node]:
        if ret[next_node] == -1:
            que.append((next_node, distance + next_distance))

for i in range(N):
    print((ret[i+1]))



#!/usr/bin/env python3
from collections import deque

n = int(input())
g = [list() for _ in range(n)]
visited = [True] * n
coler = [0] * n
for _ in range(1, n):
    v1, v2, w = map(int, input().split())
    v1 -= 1
    v2 -= 1
    w %= 2
    g[v1].append((v2, w))
    g[v2].append((v1, w))

q = deque([0])
visited[0] = False
while q:
    a = q.pop()
    for v, w in g[a]:
        if visited[v]:
            visited[v] = False
            coler[v] = (coler[a] + w) % 2
            q.append(v)

print(*coler, sep="\n")


import sys
sys.setrecursionlimit(10**7)
N = int(input())

Graph = [[] for _ in range(N+10)]
dist  = [10000000000000]*(N+10)

for i in range(N-1):
	u,v,w = map(int,input().split())
	u-=1
	v-=1
	Graph[u].append((v,w))
	Graph[v].append((u,w))

dist[0] = 0

def func(fromE,now,length):
	if fromE != -1:
		dist[now] = dist[fromE]+length
	for i in range(len(Graph[now])):
		target = Graph[now][i][0]
		lengt  = Graph[now][i][1]

		if target == fromE:
			continue

		func(now,target,lengt)

func(-1,0,0)

for i in range(N):
	if dist[i]%2 == 0:
		print(0)
	else:
		print(1)

import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    def dfs(node):
        for adjnode in edges[node]:
            if colors[adjnode[0]] == -1:
                if adjnode[1] % 2 == 0:
                    colors[adjnode[0]] = colors[node]
                else:
                    colors[adjnode[0]] = colors[node] ^ 1
                dfs(adjnode[0])
    # input
    n = int(input())
    edges = {e: [] for e in range(n)}
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        edges[u].append((v, w))
        edges[v].append((u, w))
    # process
    colors = [-1] * n
    colors[0] = 0
    dfs(0)
    # output
    print(*colors, sep='\n')


def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10**7)

N = int(input())
links = [[] for _ in range(N)]
result = [0 for _ in range(N)]
memo = [0 for _ in range(N)]
for _ in range(N-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  links[u].append([v, w])
  links[v].append([u, w])
def color(u):
  if memo[u]:
    return
  for l in links[u]:
    result[l[0]] = abs(l[1]%2-result[u])
  memo[u] = 1
  for l in links[u]:
    color(l[0])
color(0)
for r in result:
  print(r)

from collections import deque

N = int(input())
dist = {}
graph = [[] for i in range(N)]

for i in range(1, N):
    u, v, w = list(map(int, input().split()))
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)
    dist[(u-1, v-1)] = w


q = deque()
q.append(0)

color = [-1] * N
color[0] = 0

while q:
    now = q.popleft()

    for adj in graph[now]:
        if color[adj] == -1:
            if now < adj:
                color[adj] = color[now] + dist[(now, adj)]
            else:
                color[adj] = color[now] + dist[(adj, now)]

            q.append(adj)


for i in range(N):
    print((color[i] % 2))


from collections import deque

N = int(input())
conn = [[] for _ in range(N + 1)]
for i in range(N - 1):
    u, v, w = [int(x) for x in input().split()]
    conn[u].append([v, w])
    conn[v].append([u, w])

q = deque([1])
d = [-1]* (N + 1)
d[1] = 0
while q:
    u = q.popleft()
    for e in conn[u]:
        v, w = e[0], e[1]
        if d[v] == -1:
            d[v] = d[u] + w
            q.append(v)

for v in range(1, N + 1):
    print(d[v] % 2)

import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *UVW = map(int, read().split())
    G = [[] for _ in range(N)]
    for u, v, w in zip(*[iter(UVW)] * 3):
        G[u - 1].append((v - 1, w))
        G[v - 1].append((u - 1, w))

    dist = [INF] * N
    dist[0] = 0
    hq = [(0, 0)]

    while hq:
        d, v = heappop(hq)
        if d > dist[v]:
            continue
        for nv, cost in G[v]:
            if dist[nv] > dist[v] + cost:
                dist[nv] = dist[v] + cost
                heappush(hq, (dist[nv], nv))

    ans = [0] * N
    for i in range(N):
        ans[i] = 0 if dist[i] % 2 == 0 else 1

    print(*ans, sep='\n')
    return


def __starting_point():
    main()

__starting_point()

from collections import defaultdict, deque
 
 
def bfs(start):
    q = deque([start])
    dist = [-1] * N
    dist[start] = 0
    while q:
        v = q.popleft()
        for nv, nw in g[v]:
            if dist[nv] >= 0:
                continue
            dist[nv] = (dist[v] + nw) % 2
            q.append(nv)
    return dist
 
 
N, *UVW = map(int, open(0).read().split())
g = defaultdict(set)
 
ans = [0] * N
for u, v, w in zip(*[iter(UVW)] * 3):
    u -= 1
    v -= 1
    g[u].add((v, w))
    g[v].add((u, w))
print("\n".join(map(str, bfs(0))))

def f(G, not_searched, results={0: '0'}):
    stack = []
    while len(not_searched) > 0:
        if len(stack) > 0:
            i = stack.pop()
            not_searched.remove(i)
        else:
            i = not_searched.pop()

        for key, val in G[i].items():
            if not key in not_searched:
                continue

            if val % 2 == 1:
                if results[i] == '0':
                    results[key] = '1'
                else:
                    results[key] = '0'
            else:
                results[key] = results[i]

            stack.append(key)

    return results

N = int(input())
G = [{} for _ in range(N)]
not_searched = set([i for i in range(N)])

if N == 1:
    print(results[0])
else:
    for i in range(N-1):
        u, v, w = map(int, input().split())
        G[u-1][v-1] = w
        G[v-1][u-1] = w

    results = f(G, not_searched)
    for i in range(N):
        print(results[i])

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())

edges = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    edges[u-1].append((v-1, w))
    edges[v-1].append((u-1, w))

q = deque()
q.append((0, 0))
color = {}
while q:
    node, dist = q.popleft()
    if node in color:
        continue
    if dist % 2 == 0:
        color[node] = 0
    else:
        color[node] = 1
    for n_node, n_dist in edges[node]:
        q.append((n_node, dist+n_dist))

for i in range(N):
    print(color[i])

import sys
from collections import deque
readline = sys.stdin.readline
n = int(readline())
G = [[] for _ in range(n)]
for _ in range(n-1):
    u,v,w = map(int, readline().split())
    G[u-1].append((v-1,w))
    G[v-1].append((u-1,w))

V = [-1]*n
V[0] = 0
que = deque([0])
while que:
    nw = que.popleft()
    for nx,d in G[nw]:
        if V[nx]!=-1: continue
        V[nx] = (V[nw]+d)%2
        que.append(nx)

for v in V:
    print(v)

g = {}
a = int(input())
for i in range(a - 1):
    c = [int(s) for s in input().split()]
    if c[0] not in g: g[c[0]] = [(c[1], c[2])]
    else: g[c[0]].append((c[1], c[2]))

    if c[1] not in g: g[c[1]] = [(c[0], c[2])]
    else: g[c[1]].append((c[0], c[2]))

c = {}
d = {i: False for i in range(1, a + 1)}
c[1], d[1] = 0, True
Q = [1]
while(Q != []):
    r = Q.pop(0)
    for i in g[r]:
        if d[i[0]] == False:
            d[i[0]] = True
            Q.append(i[0])
            if i[1] % 2 == 0: c[i[0]] = c[r]
            else: c[i[0]] = (c[r] + 1) % 2
for i in range(1, a + 1): print(c[i])

from collections import deque
N = int(input())
#隣接リスト
g = [[] for i in range(N)]
for i in range(N-1):
  u,v,w = list(map(int,input().split()))
  g[u-1].append([v-1,w])
  g[v-1].append([u-1,w])
q = deque()
#通ったかどうか
check = [0] * N
check[0] = 1
q.append(0)
ans = [-1] * N
ans[0] = 0
while len(q) > 0:
  e = q.popleft()
  for i,j in g[e]:
    if check[i] == 1:
      continue
    ans[i] = (ans[e] + j) %2
    check[i] = 1
    q.append(i)
for i in range(N):
  print((ans[i]))


from collections import deque

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = list(map(int, input().split()))
    u, v = u - 1, v - 1
    graph[u].append([v, w])
    graph[v].append([u, w])

colors = [-1 for _ in range(N)]
stack = deque()
stack.append(0)
colors[0] = 0

while stack:
    n = stack.popleft()
    for _next, w in graph[n]:
        if colors[_next] != -1:
            continue
        colors[_next] = (colors[n] + w) % 2
        stack.append(_next)

for c in colors:
    print(c)


import sys
sys.setrecursionlimit(1000000)

def dfs(color, u):
    for v in conn[u]:
        if not (color[v] == -1):
            continue
        color[v] = (color[u] + weight[(u, v)]) % 2
        dfs(color, v)

N = int(input())

conn = [[] for _ in range(N + 1)]
weight = {}
for _ in range(N - 1):
    u, v, w = list(map(int, input().split()))
    conn[u].append(v)
    conn[v].append(u)
    weight[(u, v)] = w
    weight[(v, u)] = w

color = [-1]*(N + 1)
color[1] = 0
dfs(color, 1)
for i in range(1, N + 1):
    print((color[i]))


#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return list(map(int,input().split()))
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()
graph =[[]*(n+1) for i in range(n+1)]
ans = [0]*(n+1)
for i in range(n-1):
    u,v,w = list(map(int,input().split()))
    w = w%2
    graph[u].append([v,w])
    graph[v].append([u,w])
#vをcに塗る。pはvの親
def dfs(v,p,c,ans):
    ans[v] = c
    for i in graph[v]:
        if i[0] == p:
            continue
        if i[1] == 1:
            dfs(i[0],v,1-c,ans)
        if i[1] == 0:
            dfs(i[0],v,c,ans)
dfs(1,0,0,ans)
for i in ans[1:]:
    print(i)


def inpl(): return list(map(int, input().split()))
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = inpl()
    G[u-1].append((v-1, w))
    G[v-1].append((u-1, w))

Q = [(0, 0)]
searched = [0]*N
searched[0] = 1
ans = [-1]*N
ans[0] = 0

while Q:
    p, c = Q.pop()
    for q, d in G[p]:
        if searched[q]:
            continue
        ans[q] = (c+d)%2
        searched[q] = 1
        Q.append((q, ans[q]))
print(*ans, sep="\n")

n = int(input())
visited = [False] * (n + 1)
distance = [0] * (n + 1)
prev = [0] * (n + 1)

from collections import defaultdict, deque
d = defaultdict(list)

for _ in range(n-1):
    u,v,w = list(map(int, input().split()))
    d[u].append((v, w))
    d[v].append((u, w))

q = deque([1])
while q:
    node = q.popleft()
    visited[node] = True
    for next_node, next_dist in d[node]:
        if not visited[next_node]:
            q.append(next_node)
            # 距離を更新
            distance[next_node] = distance[node] + next_dist
    
# print(distance)
for dist in distance[1:]:
    print(dist%2)

# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
#import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return list(map(t, sysread().split()))
def mapread(t=int):
    return list(map(t, read().split()))

def dfs(c, num, to, cols):
    for n, nw in to[c]:
        if cols[n] == -1:
            y = (num + nw) % 2
            cols[n] = (num + nw) % 2
            dfs(n, y, to, cols)

def run():
    N = intread()
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v, w = mapline()
        to[u].append((v, w))
        to[v].append((u, w))
    cols = [-1] * (N+1)
    cols[1] = 0
    dfs(1, 0, to, cols)

    for x in cols[1:]:
        print(x)

def __starting_point():
    run()

__starting_point()

from collections import deque

N = int(input())
graph = [[] for _ in range(N)]
dist = [-1] * N
for _ in range(N-1):
  u, v, w = map(int, input().split())
  graph[u-1].append((v-1, w))
  graph[v-1].append((u-1, w))
q = deque()

dist[0] = 0
q.append(0)

while len(q) != 0:
  v = q.popleft()
  for next_v, next_w in graph[v]:
    if dist[next_v] != -1:
      continue
    dist[next_v] = dist[v] + next_w
    q.append(next_v)

for d in dist:
  if d%2 == 0:
    print(0)
  else:
    print(1)

from collections import defaultdict

N = int(input())
edges = defaultdict(list)
for _ in range(N-1):
    u, v, w = map(int, input().split())
    u-=1
    v-=1
    edges[u].append((v, w))
    edges[v].append((u, w))

colors = [None] * N

stack = [(0, 0)]

while stack:
    u, c = stack.pop()
    if colors[u] != None:
        continue
    colors[u] = c
    for v, w in edges[u]:
        stack.append((v, (c+w)%2))

for u in range(N):
    print(colors[u])

from collections import deque

N=int(input())
G=[{} for _ in range(N+1)]

for i in range(N-1):
  u,v,w=map(int,input().split())
  G[u][v]=w
  G[v][u]=w
  
for i in range(1,N+1):
  if len(G[i])==1:
    start=i
    break

def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque([])
    now = s
    seen[now]=1
    todo.append(now)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + G[a][b]
    return d

d = bfs(start)
for i in range(1,N+1):
  d_ = d[i]
  if d_ % 2 == 0:print(0)
  else:print(1)

import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def search(nodes, searched, labels, v):
  searched[v] = 1
  label = labels[v]
  for l in nodes[v]:
    x, w = l
    if not searched[x]:
      if w %2 == 0:
        labels[x] = label
      else:
        labels[x] = (label + 1) % 2
      search(nodes, searched, labels, x)

def solve(n, nodes):
  searched = [0]*n
  labels = [None]*n
  labels[0] = 0
  search(nodes, searched, labels, 0)
  return labels

def main():
  n = int(input())
  nodes = [[] for _ in range(n)]
  for _ in range(n-1):
    v, u, w = map(int, input().split(' '))
    nodes[v-1].append((u-1,w))
    nodes[u-1].append((v-1,w))
  ans = solve(n, nodes)
  for r in ans:
    print(r)
  

def __starting_point():
  main()
__starting_point()

from collections import deque

N = int(input())

length = {}
conn = [[] for _ in range(N + 1)]
for i in range(N - 1):
    u, v, w = [int(x) for x in input().split()]
    conn[u].append(v)
    conn[v].append(u)
    length[(u, v)] = w

q = deque([1])
dist = [-1] * (N + 1)
dist[1] = 0
while q:
    u = q.popleft()
    for v in conn[u]:
        if dist[v] == -1:
            if u < v:
                dist[v] = dist[u] + length[(u, v)]
            else:
                dist[v] = dist[u] + length[(v, u)]
            q.append(v)

for i in range(1, N + 1):
    print(dist[i] % 2)

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = LI()
        G[u-1].append((v - 1, w))
        G[v-1].append((u - 1, w))

    # print(G)

    ans = [-1] * N
    ans[0] = 0
    visited = [False] * N

    def dfs(c):
        visited[c] = True
        for n, w in G[c]:
            if not visited[n]:
                if w % 2 == 0:
                    ans[n] = ans[c]
                else:
                    ans[n] = 1 - ans[c]
                dfs(n)

    dfs(0)

    for i in ans:
        print(i)

def __starting_point():
    resolve()

__starting_point()

from collections import deque
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
  u, v, w = map(int, input().split())
  g[u-1].append((v-1,w))
  g[v-1].append((u-1,w))
ds = [-1]*n
dq = deque([0])
ds[0] = 0
while dq:
  t = dq.popleft()
  for i in g[t]:
    if ds[i[0]] == -1:
      ds[i[0]] = ds[t] + i[1]
      dq.append((i[0]))
for i in ds:
  if i%2 == 0:
    print(0)
  else:
    print(1)

import heapq

def dijkstra(G, s, dist):
    dist[s] = 0
    Q = [[0,s]]
    heapq.heapify(Q)

    while(len(Q) > 0):
        cur_d, cur_v = heapq.heappop(Q)
        cur_d *= -1
        
        if(cur_d > dist[cur_v]): continue

        for e in G[cur_v]:
            to, cost = e[0], e[1]
            if(dist[cur_v] + cost < dist[to]):
                dist[to] = dist[cur_v] + cost
                heapq.heappush(Q, [-dist[to], to])

N = int(input())

G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = list(map(int,input().split()))
    u, v = u-1, v-1
    G[u].append([v,w])
    G[v].append([u,w])

dist = [1e18] * N
dijkstra(G,0,dist)

for d in dist:
    if d % 2 == 0:
        print((0))
    if d % 2 == 1:
        print((1))



#!/usr/bin python3
# -*- coding: utf-8 -*-

# 二分グラフ
N = int(input())
graph = [[] for _ in range(N)]
color = [-1]*N

# 隣接リストの作成
for i in range(N-1):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    w %= 2
    graph[a].append((b,w))
    graph[b].append((a,w))

next_q = [(0, 0)]
while len(next_q)>0:
    nw, nc = next_q.pop()
    color[nw] = nc
    for nxt, nl in graph[nw]:
        if color[nxt]==-1:
            next_q.append((nxt,(nl+nc)%2))
for i in color:
    print(i)

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    dist = [-1]*n
    que = deque([0])
    dist[0] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in g[v]:
            if dist[w[0]] > -1:
                continue
            dist[w[0]] = d + w[1]
            que.append(w[0])
    return dist

n = INT()
g = [[] for i in range(n)]
for i in range(n-1):
    x, y, z = MAP()
    g[x-1].append([y-1, z])
    g[y-1].append([x-1, z])
for k in bfs():
    print(0 if k%2 == 0 else 1)

def abc126_d():
    import sys
    sys.setrecursionlimit(10010010)
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    N = next(inp)
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        u = next(inp) - 1
        v = next(inp) - 1
        w = next(inp)
        G[u].append((v, w))
        G[v].append((u, w))

    color = [-1] * N
    color[0] = 0

    def dfs(u):
        for v, w in G[u]:
            if color[v] != -1: continue
            if w % 2 == 0:
                color[v] = color[u]
            else:
                color[v] = abs(color[u] - 1)
            dfs(v)

    dfs(0)
    print(*color, sep='\n')

def __starting_point():
    abc126_d()
__starting_point()

N=int(input())
tree=[[] for i in range(N)]
for i in range(N-1):
  u,v,w=map(int,input().split())
  tree[u-1].append((v-1,w))
  tree[v-1].append((u-1,w))
h=[]
h.append(0)
distance=[-1 for i in range(N)]
distance[0]=0
while h:
  k=h.pop(0)
  for v in tree[k]:
    x=v[0]
    y=v[1]
    if distance[x]==-1:
      distance[x]=distance[k]+y
      h.append(x)
for i in range(N):
  if distance[i]%2==0:
    print(0)
  else:
    print(1)

from collections import deque
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append([v, w])
    g[v].append([u, w])
used = [0]*n
used[0] = 1
parity = [-1]*n
parity[0] = 0
que = deque()
que.append(0)
while que:
    # print(que)
    v = que.popleft()
    for nv, w in g[v]:
        if used[nv]:
            continue
        parity[nv] = (parity[v] + w)%2
        used[nv] = 1
        que.append(nv)

# print(used)
for i in range(n):
    print(parity[i])

from collections import deque, defaultdict
n = int(input())
l = []
dc = [-1]*n
d = defaultdict(list)
for i in range(n-1):
  u,v,w = list(map(int,input().split()))
  w %= 2
  d[u-1].append([v-1,w])
  d[v-1].append([u-1,w])
# print(d)

Q = deque()
Q.append(0)
dc[0] = 0
while Q:
  q = Q.pop()

  for v,w in d[q]:
    if dc[v] == -1:
      dc[v] = (dc[q] +w)%2
      Q.append(v)

for i in dc:
  print(i)


#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc126/tasks/abc126_d


class Graph():

    def __init__(self):
        self.adjacency_dict = {}
        self.weight = []
    
    def add_vertex(self, v):
        self.adjacency_dict[v] = []
        self.weight.append([])

    def add_edge(self, v1, v2, w):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
        self.weight[v1].append(w)
        self.weight[v2].append(w)

    def get_vertexes(self):
        return list(self.adjacency_dict.keys())

    def get_edges(self, v):
        return self.adjacency_dict[v], self.weight[v]

    def print_graph(self):
        print((self.adjacency_dict))

n = int(input())

res = []
g = Graph()
for i in range(n):
    res.append(-1)
    g.add_vertex(i)

for i in range(n-1):
    u, v, w = list(map(int, input().strip().split()))
    g.add_edge(u-1, v-1, w % 2)

q = []
res[0] = 0
q.append(0)
while(len(q) > 0):
    v = q.pop()
    u_l, w_l = g.get_edges(v)
    for u, w in zip(u_l, w_l):
        if res[u] != -1:
            continue
        res[u] = (res[v] + w) % 2
        q.append(u)

for i in range(n):
    print((res[i]))


from collections import deque

n=int(input())
ch=0
g=[[] for _ in range(n)]
k=[[] for _ in range(n)]
for i in range(n-1):
  u,v,w=list(map(int,input().split()))
  if w%2==0:
    g[u-1].append(v-1)
    g[v-1].append(u-1)
  else:
    k[u-1].append(v-1)
    k[v-1].append(u-1)
    ch1=u-1
    ch2=v-1
    ch=1

## 0:White 1:Black
ans=[-1 for _ in range(n)]

if ch>0:
  ans[ch1]=0
  d=[ch1]
  qu=deque(d)
  while qu:
    p=qu.popleft()
    
    for gr in g[p]:
      if ans[gr]==-1:
        if ans[p]==0:
          ans[gr]=0
          qu.append(gr)
        else:
          ans[gr]=1
          qu.append(gr)
      
    for kr in k[p]:
      if ans[kr]==-1:
        if ans[p]==0:
          ans[kr]=1
          qu.append(kr)
        else:
          ans[kr]=0
          qu.append(kr)   
    
          
  for j in range(n):
    print((ans[j]))
    
else:
  for j in range(n):
    print((0))
      
  



import sys
sys.setrecursionlimit(1<<30)

N = int(input())
def dfs(x):
    for y in Tree[x]:
        if Parent[x] != y:
            Parent[y] = x
            distance[y] += Web[min(x,y),max(x,y)]+distance[x]
            dfs(y)
Tree = [[] for i in range(N+1)]
Parent = [0]*(N+1)
Web = dict()
for i in range(N-1):
    a,b,w = map(int,input().split())
    Tree[a].append(b)
    Tree[b].append(a)
    Web[(min(a,b),max(a,b))] = w
distance = [0]*(N+1)
dfs(1)
for i in distance[1:]:
    if i%2 == 0:
        print(1)
    else:
        print(0)

import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(20000000)
 
 
def main():
  N = int(input())
  G = [[] for _ in range(N+1)]
  for i in range(N-1):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
 
  color = [-1]*(N+1)
  color[1] = 0
  # S = [1]
  # while len(S):
  #   now = S[-1]
  #   for next_, w in G[now]:
  #     if color[next_] != -1:
  #       continue
  #     S.append(next_)
  #     color[next_] = (w % 2) ^ color[now]
  #     break
  #   else:
  #     S.pop()
 
  def dfs(now):
    for next_, w in G[now]:
      if color[next_] == -1:
        color[next_] = (w % 2) ^ color[now]
        dfs(next_)
  dfs(1)
 
  for i in range(1, N+1):
    print(color[i])
 
 
if(__name__ == '__main__'):
  main()

#import math
#import itertools
from collections import deque

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

class Graph():
    def __init__(self, v):
        self.v = v
        self.graph = [[] for _ in range(v)]
        self.INF = 10 ** 9
    
    def addEdge(self, start, end, dist):
        self.graph[start].append((end, dist))
        self.graph[end].append((start, dist))

def do():
    n=INT()
    g=Graph(n)
    for i in range(n-1):
        u,v,d=INTM()
        u-=1
        v-=1
        g.addEdge(u,v,d)

    que=deque()
    check=[True]*n
    dists=[-1]*n
    check[0]=False
    dists[0]=0
    que.append([0,0])
    while que:
        now,dist_f=que.popleft()
        for next,dist in g.graph[now]:
            if check[next]:
                check[next]=False
                temp=dist_f+dist
                dists[next]=temp
                que.append([next,temp])

    for i in dists:
        if i%2==0:
            print(0)
        else:
            print(1)
    
def __starting_point():
    do()
__starting_point()

import _heapq
inf=float("inf")


def prim():
    color=["white" for _ in range(n+1)]
    D=[inf for _ in range(n+1)]
    M=[[] for _ in range(n+1)]

    for u,v,w in UVW:
        M[u].append([w,v])
        M[v].append([w,u])

    queue=[[0,1]]
    _heapq.heapify(queue)
    color[1]="gray"
    D[1]=1

    while len(queue)>0:
        num=_heapq.heappop(queue)[1]
        if color[num]=="black":continue
        color[num]="black"

        for i,j in M[num]:
            if D[j]>i and color[j]!="black":
                if i%2==0:D[j]=D[num]
                else:D[j]=-D[num]
                color[j]="gray"
                _heapq.heappush(queue,[i,j])

    return D[1:]


n=int(input())
UVW=[list(map(int,input().split())) for _ in range(n-1)]
for i in prim():
    if i==1:print(i)
    else:print(0)