Problem:
 Score : 400 points    Problem Statement 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 1 3
1 2 2
2 3 1      Sample Output 1 0
0
1       Sample Input 2 5
2 5 2
2 3 10
1 3 8
3 4 2      Sample Output 2 1
0
1
0
1

Solution (Python):
import queue


def even_relation(N: int, edges: list)->list:
    color = [-1] * N
    color[0] = 0

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

    q = queue.Queue()
    q.put((0, -1))

    while not q.empty():
        u, par = q.get()

        for v, w in g[u]:
            if v == par:
                continue

            if w % 2 == 0:
                color[v] = color[u]
            else:
                color[v] = 1-color[u]

            q.put((v, u))

    return color


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(int(s) for s in input().split()) for _ in range(N-1)]

    for ans in even_relation(N, edges):
        print(ans)

Solution (Python):
import sys
from collections import deque


fin = sys.stdin.readline
N = int(fin())
adj = [[] for _ in range(N)]
w = {}
for _ in range(N - 1):
    u, v, w_ = [int(elem) for elem in fin().split()]
    u -= 1
    v -= 1
    w[u, v] = w_
    w[v, u] = w_
    adj[u].append(v)
    adj[v].append(u)

que = deque()
que.append([0, 0])
color_of_node = [-1] * N

while que:
    node, dist = que.popleft()
    if dist % 2 == 0:
        color_of_node[node] = 0
    else:
        color_of_node[node] = 1
    for neighbor in adj[node]:
        if color_of_node[neighbor] == -1:
            que.append([neighbor, dist + w[node, neighbor]])

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

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
n=int(input())
Edges=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    u-=1; v-=1
    w%=2
    Edges[u].append((v,w))
    Edges[v].append((u,w))
Dist=[0]*n
Visited=[False]*n
q=deque()
q.append((0,0))
while q:
    fr,dist=q.popleft()
    for to,d in Edges[fr]:
        if not Visited[to]:
            q.append((to,dist+d))
            Dist[to]=dist+d
            Visited[to]=True
for i in range(n):
    print(Dist[i]%2)

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = int(input())

lines = defaultdict(set)
for i in range(N-1):
    u,v,w = inpl()
    u,v = u-1,v-1
    lines[u].add((v,w))
    lines[v].add((u,w))

ans = [0]*N

def dfs(s,c):
    global ans
    for t,d in list(lines[s]):
        if ans[t] == 0:
            if d%2 == 0:
                ans[t] = c
                dfs(t,c)
            else:
                ans[t] = -c
                dfs(t,-c)


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

Solution (Python):
import sys

inf = 10 ** 18

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

table = [[] for _ in range(N)]
for i, (ui, vi, wi) in enumerate(uvw):
    table[ui - 1].append((vi, wi))
    table[vi - 1].append((ui, wi))
    
import heapq

d = [inf] * N
d[0] = 0
prev = [None] * N

q = []
heapq.heappush(q, (0, 1))

while len(q) > 0:
    du, u = heapq.heappop(q)
    for v, wv in table[u - 1]:
        alt = d[u - 1] + wv
        if d[v - 1] > alt:
            d[v - 1] = alt
            prev[v - 1] = u
            heapq.heappush(q, (alt, v))


for di in d:
    print(di % 2)

Solution (Python):
from sys import stdin, stdout, setrecursionlimit as lim

lim(100003)

n = input()
inp = stdin.readlines()

g = [[] for i in xrange(n + 1)]

for line in inp:
    u, v, w = map(int, line.strip().split())
    g[u].append([v, w])
    g[v].append([u, w])

out = [0] * (n + 1)
vis = [0] * (n + 1)

def dfs(u, par, z):
    global out
    
    if z & 1: out[u] = out[par] ^ 1
    else: out[u] = out[par]
    vis[u] = 1
    for v, w in g[u]:
        if vis[v] == 1: continue
        dfs(v, u, w)

dfs(1, 1, 0)

stdout.write("\n".join(map(str, out[1:])))

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop


def dijkstra(graph: list, node: int, start: int) -> list:
    
    INF = float("inf")
    dist = [INF] * node

    
    dist[start] = 0
    heap = [(0, start)]

    
    while heap:
        cost, cur_node = heappop(heap)

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))

    return dist

n = ni()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    u,v,w = li()
    u -= 1
    v -= 1
    graph[u].append((w, v))
    graph[v].append((w, u))

dist = dijkstra(graph, n, 0)

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

Solution (Python):
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for u,v,w in src:
    u,v = u-1,v-1
    es[u].append((v,w))
    es[v].append((u,w))

visited = [0]*N
visited[0] = 1
ans = [0]*N
stack = [0]

while stack:
    v = stack.pop()
    for to,c in es[v]:
        if visited[to]: continue
        ans[to] = (ans[v]+c)%2
        visited[to] = 1
        stack.append(to)
print(*ans, sep='\n')

Solution (Python):

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

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

color = [None]*N
color[0] = False
stack = [0]

while stack:
    u = stack.pop()
    for v,w in adj[u]:
        if color[v] is None:
            color[v] = (w%2) ^ color[u]
            stack.append(v)

for c in color:
    print(1 if c else 0)

Solution (Python):
import sys
sys.setrecursionlimit(114514)

N=int(input())

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

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

def walk(i, c):
	if d[i] == -1:
		d[i] = c
		for x,w in path[i]:
			walk(x, c+w)

walk(1, 0)

for c in d[1:]:
	print(c % 2)

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

Ans = [-1]*(N+1)
Ans[1] = 0
q = [1]
Closed = [False]*(N+1)
Closed[1] = True
while len(q):
    v = q.pop()
    col = Ans[v]
    for u, w in E[v]:
        if not Closed[u]:
            Closed[u] = True
            q.append(u)
            Ans[u] = col if w%2==0 else 1-col
print(*Ans[1:], sep="\n")

Solution (Python):

import sys
sys.setrecursionlimit(200000)

def dfs(idx, color, colors, conn, visited):
    visited[idx] = True
    colors[idx] = color
    for node, w in conn[idx]:
        if visited[node]:
            continue
        if w % 2 == 0:
            colors = dfs(node, color, colors, conn, visited)
        else:
            colors = dfs(node, (color + 1) % 2, colors, conn, visited)
    return colors


def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[u[i] - 1].append([v[i] - 1, w[i]])
        conn[v[i] - 1].append([u[i] - 1, w[i]])
    colors = [-1] * N
    visited = [False] * N
    colors = dfs(0, 0, colors, conn, visited)
    
    
    
    
    
    
    
    
    for c in colors:
        print(c)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    u = [int()] * (N-1)  
    v = [int()] * (N-1)  
    w = [int()] * (N-1)  
    for i in range(N-1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())

EDGE=[list(map(int,input().split())) for i in range(N-1)]

E=[[] for i in range(N+1)]

for x,y,w in EDGE:
    E[x].append([y,w])
    E[y].append([x,w])

from collections import deque
QUE = deque([1])

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

while QUE:
    now=QUE.pop()

    for to,w in E[now]:
        if check[to]!=-1:
            continue
        check[to]=(check[now]+w)%2
        QUE.append(to)

for c in check[1:]:
    print(c)

Solution (Python):
from collections import deque


n = int(input())
info = [list(map(int, input().split())) for i in range(n-1)]
tree = [[] for i in range(n)]

for i in range(n-1):
    tree[info[i][0] - 1].append([info[i][1] - 1, info[i][2]])
    tree[info[i][1] - 1].append([info[i][0] - 1, info[i][2]])
    
q = deque()
q.append(0)
visited = [False]*n
visited[0] = True
color = [0]*n

while q:
    pos = q.pop()
    for i, cost in tree[pos]:
        if not visited[i]:
            visited[i] = True
            if cost % 2 == 0:
                color[i] = color[pos]
            else:
                color[i] = color[pos]^1
            q.append(i)
for i in range(n):
    print(color[i])

Solution (Python):

import sys
import heapq
INF = float("inf")



class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):

    g = Graph(N)
    for _u, _v, _w in zip(u, v, w):
        g.add_edge([_u-1, _v-1, _w])  

    dist, prev = shortestPath(g, 0)

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    u = [int()] * (N-1)  
    v = [int()] * (N-1)  
    w = [int()] * (N-1)  
    for i in range(N-1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N = int(single_input())
    edge = [[] for i in range(N)]
    for i in range(N-1):
        u, v, w = map(int, line_input())
        edge[u-1].append((v-1, w))
        edge[v-1].append((u-1, w))
    
    col = [-1] * N
    que = collections.deque()
    que.append((0, 0))
    while que:
        nownode, nowdist = que.popleft()
        if col[nownode] == -1:
            col[nownode] = nowdist
            for nextnode, weight in edge[nownode]:
                if col[nextnode] == -1:
                    que.append((nextnode, nowdist + weight))
    for i in range(N):
        print(col[i] % 2)

    return 0
  
if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n,k = LI()
    s = input()
    for i in range(k-1):
        print(s[i],end = "")
    print(s[k-1].lower(),end = "")
    for i in range(k,n):
        print(s[i],end = "")
    print()
    return


def B():
    s = S()
    k = int(s[0])*10+int(s[1])
    l = int(s[2])*10+int(s[3])
    if k == 0:
        if l == 0:
            print("NA")
        elif l < 13:
            print("YYMM")
        else:
            print("NA")
    elif k < 13:
        if l == 0:
            print("MMYY")
        elif l < 13:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    else:
        if l == 0:
            print("NA")
        elif l < 13:
            print("YYMM")
        else:
            print("NA")


def C():
    n,k = LI()
    ans = 0
    for i in range(1,n+1):
        l = k/i
        ans += 1/n*1/(2 << max(0,math.ceil(math.log(l,2))))
    print(ans*2)
    return


def D():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y,w = LI()
        x -= 1
        y -= 1
        v[x].append((y,w))
        v[y].append((x,w))
    ans = [0 for i in range(n)]
    bfs_map = [1 for i in range(n)]
    bfs_map[0] = 0
    q = deque()
    q.append(0)
    while q:
        x = q.popleft()
        for y,w in v[x]:
            if bfs_map[y]:
                if w%2:
                    ans[y] = ans[x]^1
                else:
                    ans[y] = ans[x]
                bfs_map[y] = 0
                q.append(y)
    for i in ans:
        print(i)
    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    D()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
N=int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    table[u].append((v,w))
    table[v].append((u,w))
visit=[-1]*N
H=deque()
H.append(0)
visit[0]=0
while H:
    x=H.popleft()
    for y,w in table[x]:
        if visit[y]==-1:
            visit[y]=(visit[x]+w)%2
            H.append(y)
for i in range(N):
    print(visit[i])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

N = input()
W = [[] for _ in range(N)]
E = [[] for _ in range(N)]
for i in range(N-1):
  u, v, w = map(int, raw_input().split())
  E[u-1] += [v-1]
  W[u-1] += [w]
  E[v-1] += [u-1]
  W[v-1] += [w]

ans = [0]*N
def f(v, p, c):
  ans[v] = c
  for e, w, in zip(E[v], W[v]):
    if e!=p:
      f(e, v, c if w%2==0 else 1-c)
f(0, -1, 0)

for a in ans:
  print a

Solution (Python):
import sys
range = xrange
input = sys.stdin.readline

n = int(input())

coupl = [[] for _ in range(n)]
weight = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,w = [int(x) for x in input().split()]
    coupl[a-1].append(b-1)
    weight[a-1].append(w)

    coupl[b-1].append(a-1)
    weight[b-1].append(w)


depth = [0]*n
found = [False]*n

stack = [0]
found[0] = True
while stack:
    node = stack.pop()
    for nei,w in zip(coupl[node],weight[node]):
        if not found[nei]:
            found[nei] = True
            depth[nei] = depth[node] + w
            stack.append(nei)

print '\n'.join(str(x%2) for x in depth)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
colors = [2 for _ in range(n)]
adj = [[] for _ in range(n)]

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

def dfs(v):
	for c, d in adj[v]:
		if colors[c] < 2:
			continue
		if d == 0:
			colors[c] = colors[v]
			dfs(c)
		else:
			colors[c] = abs(1 - colors[v])
			dfs(c)
	return 

colors[0] = 0
dfs(0)
print(*colors, sep="\n")

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
G = [[] for i in range(N)]
C = [-1] * N
for i in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append((v, w))
    G[v].append((u, w))


def dfs(u, p, d):
    if C[u] != -1:
        return
    if d % 2 == 0:
        C[u] = 0
    else:
        C[u] = 1

    for w, c in G[u]:
        if w == p:
            continue
        dfs(w, u, d + c)


dfs(0, -1, 0)
for c in C:
    print(c)

Solution (Python):
import sys
sys.setrecursionlimit(20000000)

n = int(input())
g = [[] for i 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])
ans = [-1]*n
def dfs(x,y):
    for i,j in g[x]:
        if ans[i] == -1:
            ans[i] = (y+j)%2
            dfs(i,y+j)
dfs(0,0)
for i in ans:
    print(i)

Solution (Python):
from collections import deque
import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, readline().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))

used = [0]*N
que = deque([0])
used[0] = 1
ans = [0]*N
while que:
    v = que.popleft()
    l = ans[v]
    for w, c in G[v]:
        if used[w]:
            continue
        if c % 2:
            ans[w] = l^1
        else:
            ans[w] = l
        que.append(w)
        used[w] = 1
print(*ans, sep='\n')

Solution (Python):
N=int(input())
G=[dict() for i in range(N)]
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
color=[-1 for i in range(N)]
dist=[-1 for i in range(N)]
dist[0]=0
q=[0]
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[r][p]
        q.append(p)
for i in range(N):
    color[i]=dist[i]%2
for ans in color:
    print(ans)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**8)
N=int(input())
Graph=[[] for i in range(N)]
for i in range(N-1):
  u,v,w=map(int,input().split())
  w%=2
  Graph[u-1].append((v-1,w))
  Graph[v-1].append((u-1,w))
  
root=0
color=[-1]*N
color[0]=0
def dfs(x):
  for i,w in Graph[x]:
    if color[i]==-1:
      color[i]=(color[x]+w)%2
      dfs(i)
dfs(0)
for i in range(N):
  print(color[i])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n = I()
    aa = [LI() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b,c in aa:
        e[a].append((b,c))
        e[b].append((a,c))

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d
    d = search(1)
    rr = []
    for i in range(1,n+1):
        rr.append(d[i]%2)

    return '\n'.join(map(str, rr))


print(main())

Solution (Python):
import sys

n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    u, v, w = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, w))
    links[v].add((u, w))
ans = [-1] * n
q = [(0, 0, -1)]
while q:
    v, d, p = q.pop()
    if d % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u, w in links[v]:
        if u == p:
            continue
        q.append((u, d + w, v))
print('\n'.join(map(str, ans)))