Harryxun/stf_run huggingface dataset:
friend_dic = {}
block_dic = {}

N, M, K = map(int, input().split())

for i in range(N):
    friend_dic[i+1] = []
    block_dic[i+1] = []

for _ in range(M):
    a, b = map(int, input().split())
    friend_dic[a].append(b)
    friend_dic[b].append(a)

for _ in range(K):
    a, b = map(int, input().split())
    block_dic[a].append(b)
    block_dic[b].append(a)

def search_friends(n, friends):
    for my_friend in friend_dic[n]:
        if my_friend not in friends:
            friends.append(my_friend)
            search_friends(my_friend, friends)

result = []
clusters = []
for i in range(1, N+1):
    friends = []
    flag = False
    for cluster in clusters:
        if i in cluster:
            friends_set = cluster
            flag = True
            break
    if not flag:
        search_friends(i, friends)
        friends_set = set(friends)
        clusters.append(friends_set)
    result.append(str(len(friends_set-set(friend_dic[i])-set(block_dic[i])-{i})))

print(" ".join(result))


### FIXED CODE ###

class UnionFind:
    """
    parents: 各要素の親要素
             要素がrootの場合には　-(そのグループに属する要素数) を格納
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        # xが属するグループのrootを取得
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # 高い方の木の根に低い方の木の根を結合
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return - self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

      
n, m, k = map(int, input().split())

union_find = UnionFind(n)
friends_counter = {i: 0 for i in range(n)}
blocks_counter = {i: 0 for i in range(n)}

for _ in range(m):
    a, b = map(int, input().split())
    union_find.union(a-1, b-1)
    friends_counter[a-1] += 1
    friends_counter[b-1] += 1

for _ in range(k):
    c, d = map(int, input().split())
    if union_find.same(c-1, d-1):
        blocks_counter[c-1] += 1
        blocks_counter[d-1] += 1

result = []
for i in range(n):
    result.append(str(union_find.size(i) - friends_counter[i] - blocks_counter[i] - 1))

print(" ".join(result))
import math
import numpy as np
result = 0
n = int(input())
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            result +=  np.gcd.reduce((i,j,k))
print(result)


### FIXED CODE ###

from math import gcd
ans = 0
k = int(input())
for i in range(1, k+1):
	for j in range(1, k+1):
		for l  in range(1, k+1):
			ans += gcd(gcd(i, j), l)
print(ans)
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = 0
			while temp + A[ind] < ave:
				temp += A[ind]
				ind += 1
				if ind == N:
					break
			ret_BCDEs.append(BCDE + [temp])
			ret_inds.append(ind)
			if ind < N:
				ret_BCDEs.append(BCDE + [temp + A[ind]])
				ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

### FIXED CODE ###

def main():
	N = int(input())
	if N % 2:
		print(2 * N)
	else:
		print(N)
	return 0
main()
s=input()
print s[::-1]

### FIXED CODE ###

import sys
s=sys.stdin.readline().rstrip()
print s[::-1]
import collections
from math import factorial

N = int(input())
words = [input() for i in range(N)] 

ans = 0
L = []
for ix, word in  enumerate(words):
    word_list = list(word)
    word_list.sort()
    L.append(''.join(map(str, word_list)))

c = collections.Counter(L)

for i in c.values():    
    ans += factorial(i) / factorial(2) / factorial(i - 2)

print(int(ans))


### FIXED CODE ###

N = int(input())
dic = {}

for i in range(N):
    spell = ''.join(sorted(input()))
    if spell in dic.keys():
        dic[spell] += 1
    else:
        dic[spell] = 1

count = 0
for num in dic.values():
    count += sum([i for i in range(num)])

print(count)
n = int(input())
arr = []
for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
mm = []


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    m1 = childNodeNums
    m2 = childNodeStatus
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            mm.append(kk)
            dfs(childNodeIndex, arr, kk)




data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for m in mm:
    print(m)



### FIXED CODE ###

from sys import setrecursionlimit


def genid(a, b):
    if b < a:
        a, b = b, a
    return a * 100000 + b


def paint(currentNode, usedColor, parentNode, edges, colors):
    color = 1
    for childNode in edges[currentNode]:
        if childNode == parentNode:
            continue
        if color == usedColor:
            color += 1
        colors[genid(currentNode, childNode)] = color
        paint(childNode, color, currentNode, edges, colors)
        color += 1


setrecursionlimit(100000)

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

edges = [[] for _ in range(N)]
for a, b in ab:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

colors = {}
paint(0, -1, -1, edges, colors)

print(max(len(e) for e in edges))
for a, b in ab:
    print(colors[genid(a - 1, b - 1)])
import numpy as np

n = int(input())
a = np.array(map(int, input().split()))
ans_count = 0
print(ans_count)

### FIXED CODE ###

num_str = input()

print(sum([1 for a in num_str if a == '1']))
A,B,C,D,E,F = map(int,input().split())
f = F//100

per = 0

for w in range(1,f+1):
    wt = 0
    for b in range(0,w+1,B):
        if (w-b)%A == 0:
            wt = 1
            break
    if wt == 0:
        continue

    water = w*100
    sugar = w*E

    for s in range(sugar,-1,-1):
        st = 0
        for d in range(0,s+1,D):
            if (s-d)%C == 0:
                st = 1
                break
        if st == 1:
            break
    if s+water <= F and s/(s+water) > per:
        ans = [s+water,s]
        per = s/(s+water)

print(' '.join(map(str,ans)))


### FIXED CODE ###

A,B,C,D,E,F = map(int,input().split())
f = F//100

ans = [0,0]
per = -1
#水の量を100g単位ずつ全探索
for w in range(1,f+1):
    #そのような水の取り方があるか確認
    wt = 0
    for b in range(0,w+1,B):
        if (w-b)%A == 0:
            wt = 1
            break
    if wt == 0:
        continue

    water = w*100
    sugar = min(w*E,F-water)
    if ans[0] == 0:
        ans[0] = water
    st = 0
    #砂糖として考えられる量を大きい順に0gまでに全探索
    for s in range(sugar,0,-1):
        st = 0
        for d in range(0,s+1,D):
            if (s-d)%C == 0:
                st = 1
                break
        if st == 1:
            break
    if st == 1 and s+water <= F and s/(s+water) > per:
        ans = [s+water,s]
        per = s/(s+water)

print(' '.join(map(str,ans)))
while True:
    H, W =[int(i) for i in input().split ]
    if H == W == 0:
        break

    for h in range(H):
        for w in range(W):
            if h == 0 or h == H - 1 or w == 0 or w == W - 1:
               print('#', end='')
            else:
                print('.', end='')

        print()

    print()

### FIXED CODE ###

while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
        break
     
    for h in range(H):
        for w in range(W):
            if h == 0 or h == H-1 or w == 0 or w == W - 1:
                print('#', end='')
            else:
                print('.', end='')
        print()
     
    print()
def main():
    n,x,m = map(int,input().split())
    if m == 0:
        print(0)
        return
    t = [x]
    k = -1
    for _ in range(n):
        x = x**2 % m
        if x in t:
            k = x
            break
        t.append(x)
    s = t.index(k)
    if s == -1:
        print(sum(t))
        return
    else:
        ans = sum(t[0:s])
        b = t[s:len(t)]
        n -= s
        ans += sum(b) * (n//len(b))
        ans += sum(b[0:n%len(b)])
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n,x,m = map(int,input().split())
    if m == 0:
        print(0)
        return
    t = [x]
    k = -1
    for _ in range(n-1):
        x = x**2 % m
        if x in t:
            k = x
            break
        t.append(x)
    if k not in t:
        print(sum(t))
        return
    else:
        s = t.index(k)
        ans = sum(t[0:s])
        b = t[s:len(t)]
        n -= s
        ans += sum(b) * (n//len(b))
        ans += sum(b[0:n%len(b)])
        print(ans)

if __name__ == "__main__":
    main()
a,op,b=input().split()

while True:
    if op == "?":
        break
    else:
        if op == "+":
            print int(a)+int(b)
        elif op == "-":
            print int(a)-ing(b)
        elif op == "*":
            print int(a)*int(b)
        elif op == "/":
            print int(a)//int(b)
        else:
            print "error"

### FIXED CODE ###

while True:
    a, op, b = input().split()
    if op == '?':
        break
    if op == '/':
        op = '//'
    print(eval(a + op + b))
N = int (input ())
l = input ().split ()
list.sort (l, reverse=True)
a = 0
x = 0
for i in range (round(N/2)):
    x += int (l[a])
    a += 2
a = 1
y = 0
for i in range (N-(round(N/2))):
    y += int (l[a])
    a += 2
print (x-y)

### FIXED CODE ###

N = int (input ())
L = input ().split ()
l = [int(s) for s in L]
list.sort (l, reverse=True)
a = 0
x = 0
y = 0
while True:
    x += int (l[a])
    a += 1
    if a == N:
        break
    y += int (l[a])
    a += 1
    if a == N:
        break
print (x-y)
import copy
import numpy as np
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]
xh = sorted(xh, key=lambda x:(x[0]))
if d == 0:
    di = 0
else:
    di = 1 + 2*d
cnt = 0
while xh:
    c = xh.pop(0)
    cx, ch = c[0], c[1]
    if ch <= 0:
        continue
    if ch % a == 0:
        cn = ch // a
    else:
        cn = 1 + ch // a
    cnt += copy.deepcopy(cn)
    for nx in range(cx+1, cx+di+1):
        for i in range(len(xh)):
            if xh[i][0] == nx:
                xh[i][1] -= a * cn
print(cnt)

### FIXED CODE ###

from collections import deque
import sys

input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0]))
q = deque()
ca = 0
cnt = 0
for i in range(n):
    cx, ch = xh[i][0], xh[i][1]
    
    while q and q[0][0] < cx:
        qx, qa = q.popleft()
        ca -= qa
    
    if ch - ca <= 0:
        continue
    
    cn = (ch - ca + a - 1) // a
    cnt += cn
    ca += cn * a
    q.append([cx+2*d, cn*a])
    
print(cnt)
#include <bits/stdc++.h>
using namespace std;

int main() {

  int n, m;
  cin >> n >> m;
  cout << (1900*m + 100 * (n-m)) * pow(2, m);
}

### FIXED CODE ###

n, m = map(int, input().split())
t = 1900*m + 100*(n-m)
p = (2)**m
print(t*p)
def main():
    n, q = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(n - 1)]
    PX = [[int(e) for e in input().split()] for i in range(q)]

    V = dict()
    for a, b in AB:
        V[b] = a

    S = [0] * (n + 1)
    for p, x in PX:
        S[p] += x

    Ans = [0] * n
    Ans[0] = S[1]
    for i in range(1, n):
        Ans[i] += S[i + 1] + Ans[V[i + 1] - 1]

    print(*Ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque, defaultdict


def main():
    n, q = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(n - 1)]
    PX = [[int(e) for e in input().split()] for i in range(q)]

    G = defaultdict(set)
    for a, b in AB:
        G[a].add(b)
        G[b].add(a)

    Ans = [0] * (n + 1)
    for p, x in PX:
        Ans[p] += x

    Q = deque([1])
    Visited = [False] * (n + 1)
    Visited[1] = True
    while len(Q) > 0:
        v = Q.popleft()
        for vc in G[v]:
            if Visited[vc]:
                continue

            Ans[vc] += Ans[v]
            Q.append(vc)
            Visited[vc] = True

    print(*Ans[1:])


if __name__ == '__main__':
    main()
s=input()
k=int(input())-1
i=0
while True:
  if s[i]=='1':
    i+=1
  else:
    break
if i<k:
  print(s[1])
else:
  print(1)

### FIXED CODE ###

s=input()
k=int(input())
i=0
while True:
  if i<len(s) and s[i]=='1':
    i+=1
  else:
    break
if i==0:
  print(s[0])
  exit()
if i<k:
  print(s[i])
else:
  print(s[0])
import math

def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

d={'M':0,'A':0,'R':0,'C':0,'H':0}
n=int(input())
for i in range(n):
  word=input()
  if word[0] in d: d[word[0]]+=1

m = sum(d.values())
max = combinations_count(m,3)

if m<3:
  print(0)
  exit()

sub = 0
for i in d.values():
  if i>=3: sub += combinations_count(i, 3)
  if i>=2: sub += combinations_count(i, 2) * (m-2)

print(max - sub)


### FIXED CODE ###

comp='MARCH'
cnt=[0,0,0,0,0]

n=int(input())
for i in range(n):
  word=input()
  for j in range(len(comp)):
    if word[0]==comp[j]: cnt[j]+=1

ans = 0
for i in range(len(cnt)):
  for j in range(i+1, len(cnt)):
      for k in range(j+1, len(cnt)):
        ans += cnt[i]*cnt[j]*cnt[k]
        
print(ans)
h = int(input())
li = []
li.append(h)
c=1
while(h >  1):
    h= int(h/2)
    for i in range(2**c):   #計算量がクソ多くなる
        li.append(h)
    c += 1

#print(li)
print(len(li))

### FIXED CODE ###

h,a = map(int,input().split())
c = 0
while(True):
    h = h - a
    if(h <= 0):
        c += 1
        break

    c += 1

print(c)
from scipy.special import comb
N,K=list(map(int,input().split()))
mod=10**9+7
red=N-K
for i in range(1,K+1):
   print(int(comb(N-K+1,i)*comb(K-1,i-1)%mod))

### FIXED CODE ###

from scipy.special import comb
N,K=list(map(int,input().split()))
mod=10**9+7
red=N-K
for i in range(1,K+1):
   tmp=comb(N-K+1,i,exact=True)*comb(K-1,i-1,exact=True)%mod
   print(tmp)
# -*- coding: utf-8 -*-
import sys


def input():
    return sys.stdin.readline().strip()


def main(N, DATA):
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(3):
            for k in range(3):
                if j == k:
                    continue

                # ここと      ここを比較  ↓比較対象はこれ、j+ k
                dp[i][k] = max(dp[i][k], dp[i][j] + DATA[i][k])

    res = 0

    for v in range(N):
        res = max(res, dp[N - 1][v])
    print(res)


if __name__ == '__main__':
    N = int(input())
    DATA = [input().split() for _ in range(N)]
    # N = 3
    # DATA = [
    #     [10, 40, 70],
    #     [20, 50, 80],
    #     [30, 60, 90]
    # ]
    main(N, DATA)


### FIXED CODE ###

import sys

input = sys.stdin.readline

vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]

dp = [[0 for i in range(3)] for j in range(vacation+1)]
def chmax(a, b):
    if a > b:
        return a
    else:
        return b

for i in range(vacation):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + lst_happiness[i][k])
ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])
print(ans)
from math import factorial

N, A, B = map(int, raw_input().split())
v = map(int, raw_input().split())

C = [[0 for i in range(51)] for j in range(51)] #C[n][k] => nCk

for i in range(1, N+1):
    for j in rane(1, i+1):
        if (j == 0 or j == i):
            C[i][j] = 1
        else:
            C[i][j] = C[i-1][j-1] + C[i-1][j]

v.sort(reverse = True)

t = v[A-1]

ans = 0
X, Y = v.count(t), v[:A].count(t)

if (v[0] != v[A-1]):
    ans = C[X][Y]

else:
    for i in range(A, B+1):
        if(i <= X):
            ans += comb[X][i]

print float(sum(v[0:A]))/A
print ans

### FIXED CODE ###

from math import factorial

def comb(n, k):
    f = factorial
    return f(n) / f(k) / f(n-k)

N, A, B = map(int, raw_input().split())
v = map(int, raw_input().split())

v.sort(reverse = True)

print float(sum(v[0:A]))/A

X, Y = 0, 0
ans = 0

for i in range(N):
    if (v[i] == v[A-1]):
        X += 1
    if (v[i] == v[A-1]) and (i < A):
        Y += 1

if (v[0] != v[A-1]):
    ans = comb(X, Y)

else:
    for i in range(A, B+1):
        if(i <= X):
            ans += comb(X, i)

print ans
wd=["Mon","Tues","Wednes","Thurs","Fri","Satur","Sun"]
md=[0,31,29,31,30,31,30,31,31,30,31,30,31]

while 1:
    m,d = map(int, raw_input().split())
    if m==0: break
    s = sum([md[i] for i in range(month)]) + day + 2
    s = wd[s % 7]+"day"
    print s

### FIXED CODE ###

wd=["Mon","Tues","Wednes","Thurs","Fri","Satur","Sun"]
md=[0,31,29,31,30,31,30,31,31,30,31,30,31]

while 1:
    m,d = map(int, raw_input().split())
    if m==0: break
    s = sum([md[i] for i in range(m)]) + d + 2
    s = wd[s % 7]+"day"
    print s
A, B = input().split()

A = int(A)
B_float = int(B[2:])
B_int = int(B[0]) * 100

res = A * B // 100

print(int(res))

### FIXED CODE ###

A, B = input().split()

A = int(A)
B_float = int(B[2:])
B_int = int(B[0]) * 100

res = A * (B_int + B_float) // 100

print(int(res))
import sys
readline = sys.stdin.readline
N, K = map(int, input().split())
W = {map(int, sys.stdin.read().splitlines())}
ma = max(W)
def check(x):
    if x < ma:
        return False
    use = 1
    rest = x
    for w in W:
        if rest >= w:
            rest -= w
        else:
            rest = x - w
            use += 1
    return use <= K
l = 0
r = sum(W)
while r - l > 1:
    m = (r + l) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)


### FIXED CODE ###

import sys
readline = sys.stdin.readline
N, K = map(int, input().split())
W = tuple(map(int, sys.stdin.readlines()))
ma = max(W)
def check(x):
    if x < ma:
        return False
    use = 1
    rest = x
    for w in W:
        if rest >= w:
            rest -= w
        else:
            rest = x - w
            use += 1
            if use > K:
                return False
    return True
l = 0
r = sum(W)
while r - l > 1:
    m = (r + l) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)
A=int(input('A'))
B=int(input('B'))
V=int(input('V'))
W=int(input('W'))
T=int(input('T'))

if (V-W)*T >= A-B:
	print('Yes')
else
	print('No')

### FIXED CODE ###

A,V = list(map(int, input().split()))
B,W = list(map(int, input().split()))
T = int(input())
print("YES" if (V-W) * T >= abs(B-A) else "NO")
A*B

### FIXED CODE ###

a, b = map(int,input().split())
def main(x,y):
    print(x*y)

main(a,b)
n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10**9 + 7

ze = []
pl,mi = [],[]
for i in range(n):
    if a[i] < 0:
        ze.append((-a[i],1))
        mi.append(a[i])
    else:
        ze.append((a[i],0))
        pl.append(a[i])
        
ze.sort(reverse = True)
pl.sort(reverse = True)
mi.sort()

one = 0
for i in range(k):
    one += ze[i][1]
    
ans = 1
zero = k-one

if one % 2 == 0:
    for i in range(k):
        ans = ans * ze[i][0] % MOD
    print(ans)
        
elif zero == 0:
    for i in range(k):
        ans = ans * mi[n-1-i] % MOD
        print(ans)
        
else:
    if (zero == len(pl) and one == len(mi)) or len(pl) == 0:
        ak = [zero,one]
    elif (zero != len(pl) and one == len(mi)):
        ak = [zero+1,one-1]
    elif zero == len(pl) and one != len(mi):
        ak = [zero-1,one+1]
    else:
        if abs(mi[zero])/pl[one-1] >= pl[one]/abs(mi[zero-1]):
            ak = [zero+1,one-1]
        else:
            ak = [zero-1,one+1]
            
    ans = 1
    for i in range(ak[0]):
        ans = ans * pl[i] % MOD
    for i in range(ak[1]):
        ans = ans * mi[i] % MOD
        
    print(ans)

### FIXED CODE ###

from decimal import *

n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10**9 + 7

ze = []
pl,mi = [],[]
for i in range(n):
    if a[i] < 0:
        ze.append((-a[i],1))
        mi.append(a[i])
    else:
        ze.append((a[i],0))
        pl.append(a[i])
        
ze.sort(reverse = True)
pl.sort(reverse = True)
mi.sort()

one = 0
for i in range(k):
    one += ze[i][1]
    
ans = 1
zero = k-one

if one % 2 == 0:
    for i in range(k):
        ans = ans * ze[i][0] % MOD
    print(ans)
        
elif len(pl) == 0:
    for i in range(k):
        ans = ans * mi[n-1-i] % MOD
    print(ans)
        
else:
    if (zero == len(pl) and one == len(mi)) or len(pl) == 0 or len(mi) == 0:
        ak = [zero,one]
    elif (zero != len(pl) and one == len(mi)) or zero == 0:
        ak = [zero+1,one-1]
    elif zero == len(pl) and one != len(mi) or one == 0:
        ak = [zero-1,one+1]
    else:
        if Decimal(abs(mi[one]))/Decimal(pl[zero-1]) >= Decimal(pl[zero])/Decimal(abs(mi[one-1])):
            ak = [zero-1,one+1]
        else:
            ak = [zero+1,one-1]
            
    ans = 1
    for i in range(ak[0]):
        ans = ans * pl[i] % MOD
    for i in range(ak[1]):
        ans = ans * mi[i] % MOD
        
    print(ans)
N=int(input())
if N>=5*1e4:
  quit()
G=[[] for i in range(N)]
res=[0]*N
def dfs(v,p,c):
  res[v]=c
  for nv,w in G[v]:
    if nv==p:
      continue
    if (w & 1):
      dfs(nv,v,1-c)
    else:
      dfs(nv,v,c)
 
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))
dfs(0,-1,0)
for i in range(N):
  print(res[i])

### FIXED CODE ###

N=int(input())
G=[[] for i in range(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))
reached=[0]*N
stack=[0]
reached[0]=[1]
res=[-1]*N
res[0]=0
while(stack):
    v=stack.pop()
    for nv,w in G[v]:
        if reached[nv]:
            continue
        if w & 1:
            res[nv]=1-res[v]
        else:
            res[nv]=res[v]
        stack.append(nv)
        reached[nv]=1
for i in res:
    print(i)