Harryxun/stf_run huggingface dataset:
a, b = input().split(' ')
c = int(a) + int(b)
if (a%3==0 and a > 3) or (b%3==0&&b>3) or (c%3==0 &&c>3):
  print("Possible")
else:
  print("Impossible")

### FIXED CODE ###

a, b = map(int, input().split(" "))
if a % 3 == 0 or b % 3 == 0 or (a + b) % 3 == 0:
  print("Possible")
else:
  print("Impossible")
s = input()
k = int(input())
if s[0] == '1':
    print(s[1])
else:
    print(s[0])

### FIXED CODE ###

s = input()
k = int(input())
for i in range(k):
    if s[i] != '1':
        print(s[i])
        exit()
print(1)
def gcd(a,b):
  if(b==0):
    return a
  return gcd(b,a%b)

n, k = [int(x) for x in input().split()]
print(min(gcd(n,k),k-gcd(n,k))

### FIXED CODE ###

n, k = [int(x) for x in input().split()]
print(min(n%k,k-n%k))
N = int(input())

if N%1000=0:
    print(0)
else:
    print(1000-(N%1000))

### FIXED CODE ###

N = int(input())

if N%1000==0:
    print(0)
else:
    print(1000-(N%1000))
S = input().sprit()

Flag = True

if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
  Flag = False
  
if Flag == False:
  print("Bad")
else:
  print("Good")

### FIXED CODE ###

S = int(input())

Flag = True

if (S//1000) == ((S%1000)//100) or ((S%1000)//100) == ((S%100)//10) or ((S%100)//10) == ((S%10)//1):
  Flag = False
  
if Flag == False:
  print("Bad")
else:
  print("Good")
s = int(input())
a = int(s**(1/2)) + 1
b = a**2 - s
if s = 10**18:
  print(" ".join(map(str, [0,0,10**9,0,0,10*9])))
else:
  print(" ".join(map(str, [0,0,a,1,b,a])))

### FIXED CODE ###

s = int(input())
a = int(s**(1/2))
if s == a**2:
  b =0 
  print(" ".join(map(str, [0,0,a,1,b,a])))
elif a*(a+1) - s >= 0: 
  b = a*(a+1) - s
  print(" ".join(map(str, [0,0,a+1,1,b,a])))
else:
  b = (a+1)**2 - s
  print(" ".join(map(str, [0,0,a+1,1,b,a+1])))
N = input()
B = False
kaisu = 0
array = map(int,input().split())

def calc(n):
  retuen n/2
  
  
while !B:
	for i in range(N):
  		if array[i]/2 == 1:
    		B = True
  	if B == False:
    	array = map(calc, array)
    	kaisu += 1
  	else:
    	break
        
print(kaisu)
    

    

### FIXED CODE ###

N = int(input())
B = False
kaisu = 0
array = list(map(int,input().split()))

def calc(n):
  return int(n) / 2
  
  
while not B:
  for i in range(N):
    if array[i] % 2 == 1:
      B = True
  if not B:
    array = list(map(calc, array))
    kaisu += 1
  else:
    break
        
print(kaisu)
def step_memo(H):
    N = len(H)
    memo = [0]*N
    n = N-1
    def step(n):
        if n == 0:
            return 0
        elif n == 1:
            memo[1] = abs(H[1]-H[0])
            return memo[1]
        elif memo[n] != 0:
            return memo[n]
        else:
            memo[n]= min(step(n-2)+abs(H[n-2]-H[n]), step(n-1)+abs(H[n-1]-H[n]))
            return memo[n]
    return step(n)

S = int(input())
T = list(map(int, input().split()))
print(step_memo(T))

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
points = [0]*N
points[1] = abs(H[1]-H[0])
for i in range(2,N):
    points[i] = min(points[i-2]+abs(H[i-2]-H[i]), points[i-1]+abs(H[i-1]-H[i]))
print(points[-1])
print input()[::-1]

### FIXED CODE ###

print raw_input()[::-1]
from operator import mul
from functools import reduce
import numpy as np

if __name__ == '__main__':
    try:

        N = int(input())
        A = np,array(list(map(int, input().split())))
        ans = reduce(mul, A)
        if ans > 10 ** 18:
            print(-1)
        else:
            print(ans)
    except:
        if 0 in A:
            print(0)
        else:
            print(-1

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 1
for a in A:
    ans *= a
    if ans > 1000000000000000000:
            print(-1)
            quit()
print(ans)
S=list(input())

for i in range(len(S)//2):
    F=1
#    print(S[i],S[-(i+1)])
    if S[i]!=S[-(i+1)]:
        F=0
        break

N=len(S)
s=S[:N//2]
#print(s)
for i in range(N//2//2):
    FF=1
#    print(s[i],s[-(i+1)])
    if s[i]!=s[-(i+1)]:
        FF=0
        break

if F and FF:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

S=list(input())
SV=S[::-1]
N=len(S)

for i in range(N):
    F=1
    if S[i]!=SV[i]:
        F=0
        break

s=S[:N//2]
sv=s[::-1]
n=len(s)
#print(s)
for i in range(n):
    FF=1
#    print(s[i],s[-(i+1)])
    if s[i]!=sv[i]:
        FF=0
        break

if F and FF:
    print('Yes')
else:
    print('No')
import sys
sys.setrecursionlimit(1000000)

N, K = map(int, input().split())
*A, = map(int, input().split())

def g(X, t):
    if X<=t:
        return 0
    return 1+g(t, t)+g(X-t, t)

def f(t):
    c = 0
    for i in A:
        c += i//t if i!=t else 0
    return c<=K

left, right = -1, 10**10
while right-left>1:
    m = (right+left)//2
    if f(m):
        right = m
    else:
        left = m

print(right)


### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())

def f(t):
    if t!=0:
        c = 0
        for i in A:
            c += i//t if i!=t else 0
        return c<=K
    else:
        return all(i<=t for i in A)

left, right = -1, 10**10
while right-left>1:
    m = (right+left)//2
    if f(m):
        right = m
    else:
        left = m

print(right)
input_list = list(map(int, input().split()))
a = input_list[0]
b = input_list[1]
taps = 0
count = 0
taps += a
count += 1

while taps < b:
    taps += a-1
    count += 1
print(count)

### FIXED CODE ###

# abc139 a
s = input()
t = input()
count = 0
for i in range(len(s)):
    if s[i] == t[i]:
        count += 1
print(count)
s = str
End = False
S = input()
A,B,C,D = int(S[0]),int(S[1]),int(S[2]),int(S[3])
for i in [B,-1*B]:
    for j in [C,-1*C]:
        for k in [D,-1*D]:
            if A + i + j + k == 7:
                print(f"{A:d}{i:+d}{j:+d}{k:+d}=7")
                exit()

### FIXED CODE ###

S = input()
A,B,C,D = int(S[0]),int(S[1]),int(S[2]),int(S[3])
for i in [B,-1*B]:
    for j in [C,-1*C]:
        for k in [D,-1*D]:
            if A + i + j + k == 7:
                print("{:d}{:+d}{:+d}{:+d}=7".format(A,i,j,k),end="")
                exit()
def inpl(): return list(map(int, input().split()))
W, H, x, y = inpl()
if x > W/2:
    x = W-x
if y > H/2:
    y = H-y

a = W*y
b = H*x
if x == 0 or y == 0:
    print(H*W/2, 0)
    raise
elif W/H == x/y:
    print(H*W/2, int(W/2==x))
elif a > b:
    print(a, int(2*x == W))
else:
    print(b, int(2*y == H))

### FIXED CODE ###

W, H, x, y = map(int, input().split())
print(H*W/2, int((2*y == H)&(2*x == W)))
W,H,x,y,r = raw_input().split(" ")
if (x+r)<W and 0<(x-r) and 0<(y-r) and (y+r)<H:
    print "Yes"
else:
    print "No"

### FIXED CODE ###

a = raw_input().split(" ")
W = int(a[0])
H = int(a[1])
x = int(a[2])
y = int(a[3])
r = int(a[4])
if (x - r) >= 0 and (x + r) <= W and (y - r) >= 0 and (y + r) <= H:
    print "Yes"
else:
    print "No"
from collections import *
def dfs(x):
    visited[x]=True
    for i in range(len(adj[x])):
        t=adj[x][i]
        distance[t]=max(distance[t],distance[x]+1)
        indegree[t]-=1
        if(indegree[t]==0):
            dfs(t)

MAX = 10**5+5
indegree=[0]*(MAX)
distance=[0]*(MAX)
visited = [False]*(MAX)
adj = defaultdict(list)
N,M=list(map(int,input().split()))
for i in range(M):
    a,b=list(map(int,input().split()))
    adj[a].append(b)
    indegree[b]+=1
ans=0
for i in range(1,N+1):
    if(visited[i]==False and indegree[i]==0):
        dfs(i)
for i in range(1,N+1):
    ans=max(ans,distance[i])

print(ans)


### FIXED CODE ###

import sys
from collections import *
sys.setrecursionlimit(10**5)
def dfs(x):
    visited[x]=True
    for i in range(len(adj[x])):
        t=adj[x][i]
        distance[t]=max(distance[t],distance[x]+1)
        indegree[t]-=1
        if(indegree[t]==0):
            dfs(t)

MAX = 10**5+5
indegree=[0]*(MAX)
distance=[0]*(MAX)
visited = [False]*(MAX)
adj = defaultdict(list)
N,M=list(map(int,input().split()))
for i in range(M):
    a,b=list(map(int,input().split()))
    adj[a].append(b)
    indegree[b]+=1
ans=0
for i in range(1,N+1):
    if(visited[i]==False and indegree[i]==0):
        dfs(i)
for i in range(1,N+1):
    ans=max(ans,distance[i])

print(ans)
n = int(input())
d_list = list(map(int,input().split()))
d = sorted(d_list)
g = n//2
f = d[g]
j = d[g+1]
print(j-f)

### FIXED CODE ###

n = int(input())
d_list = list(map(int,input().split()))
d = sorted(d_list)
g = n//2
f = d[g-1]
j = d[g]
print(j-f)
import copy

def main():
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a%b)

    def lcm(a, b):
        return int(a / gcd(a, b)) * b
    
    n, m = map(int, input().split())
    A = set([int(x) for x in input().split()])
    A_ = copy.deepcopy(A)
    a_ = A.pop()
    for a in A:
        a_lcm = lcm(a_, a)
        a_ = a_lcm
    for i in A_:
        if a_lcm / 2 % i != 0:
            continue
        else:
            print(0)
            exit()
    if a_lcm / 2 > m:
        print(0)     
    else:
        ans = int((m - (a_lcm / 2))) // a_lcm + 1
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy
# from math import gcd


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return (a // gcd(a, b)) * b
def main():
    n, m = map(int, input().split())
    A = set([int(x) for x in input().split()])
    a_lcm = 1
    for a in A:
        a_lcm = lcm(a_lcm, a)
        # mがlcmの半分よりも小さかったら0
        if (a_lcm / 2) > m:
            print(0)
            exit()
    for a in A:
        if (a_lcm / 2) % a == 0:
            print(0)
            exit()
    # # あとは定数倍の数調べて終わり
    ans = int((m - (a_lcm / 2)) // a_lcm) + 1
    print(ans)

if __name__ == '__main__':
    main()
s = input()
temp = []
count = 0
for i in range(len(s)):
    if s[i] == 'A' or s[i] == 'C' or s[i] == 'G' or s[i] == 'T':
        count += 1
    else:
        temp.append(count)
        count = 0
print(max(temp))

### FIXED CODE ###

s = input()
temp = []
maximum = 0
count =0
for i in range(len(s)):
    if s[i] == 'A' or s[i] == 'C' or s[i] == 'G' or s[i] == 'T':
            count +=1
            maximum = max(maximum,count)
    else:
        count = 0

print(maximum)
import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

maxv = -100000000
minv = a[0]
for i in range(len(a)):
    maxv = max(sub,b[i]-minv)
    minv = min(minv,b[i])

print(sub)




### FIXED CODE ###

import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

maxv = -1000000000
minv = a[0]
for i in range(len(a)):
    maxv = max(maxv,b[i]-minv)
    minv = min(minv,b[i])
print(maxv)
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    if a%m!=0:
      x = extgcd(a,m)[0]
      return (m+x%m)%m
      

#nCk mod m を計算する(デフォルトの引数は10**9+7)
def c_mod(n,k,m=10**9+7):
  res = 1
  for i in range(1,n+1):
      if (i%m)!=0:
        res = res*i%m
      else:
        res=res/i%m
  for i in range(1,k+1):
      if (i%m)!=0:
        res = res*mod_inv(i,m)%m
      else:
        res=res/i%m
  for i in range(1,n-k+1):
      if (i%m)!=0:
        res = res*mod_inv(i,m)%m
      else:
        res=res/i%m
  return res


x,y=map(int,input().split())
if (2*x-y)%3==0 and (2*y-x)%3==0 and (2*y-x)>0 and (2*x-y)>0 :
  l=int((2*x-y)/3)
  k=int((2*y-x)/3)
  ans=c_mod(l+k,k)

else:
  ans=0
print(ans)


### FIXED CODE ###

r=int(input())
print(r**2)
from itertools import accumulate

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

acc1 = list(accumulate(A))
acc2 = list(accumulate(B))

def is_ok(a, b):
    if acc1[a] + acc2[b] <= K:  return 1
    return 0

def binary_search(i, left, right):
    while (abs(right - left) > 1):
        mid = (left + right) // 2
        if is_ok(i, mid):  right = mid
        else:  left = mid
    return right

ans = 0
for i in range(N):
    ret = binary_search(i, M, -1)
    if ret == -1:  
      if acc1[i] <= K:  ans = max(i + 1, ans)
    else:
      ans = max(ans,  i + ret + 2)
      
acc1, acc2 = acc2, acc1
      
for i in range(N):
    ret = binary_search(i, M, -1)
    if ret == -1:  
      if acc1[i] <= K:  ans = max(i + 1, ans)
    else:
      ans = max(ans,  i + ret + 2)
      
print(ans)

### FIXED CODE ###

from itertools import accumulate

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

acc1 = list(accumulate(A))
acc2 = list(accumulate(B))

def is_ok(a, b):
    if acc1[a] + acc2[b] <= K:  return 1
    return 0

def binary_search(i, left, right):
    while (abs(right - left) > 1):
        mid = (left + right) // 2
        if is_ok(i, mid):  right = mid
        else:  left = mid
    return right

ans = 0
for i in range(N):
    ret = binary_search(i, M, -1)
    if ret == -1:  
      if acc1[i] <= K:  ans = max(i + 1, ans)
    else:
      ans = max(ans,  i + ret + 2)
      
acc1, acc2 = acc2, acc1
N, M = M, N
      
for i in range(N):
    ret = binary_search(i, M, -1)
    if ret == -1:  
      if acc1[i] <= K:  ans = max(i + 1, ans)
    else:
      ans = max(ans,  i + ret + 2)
      
print(ans)
N = int(input())
SP = []
for _ in range(N):
  SP.append([i for i in input().split()])
for n in range(N):
  SP[n][1] = str(100 - SP[n]).rjust(3,'0')
SP2 = []
for n in range(N):
  SP2.append(SP[0]+SP[1])
ans = sorted(range(len(SP2)), key=lambda k: SP2[k])
[print(i) for i in ans]

### FIXED CODE ###

N = int(input())
SP = []
for _ in range(N):
    SP.append([i for i in input().split()])
for n in range(N):
    SP[n][1] = str(100 - int(SP[n][1])).rjust(3,'0')
SP2 = []
for n in range(N):
    SP2.append(SP[n][0]+SP[n][1])
ans = sorted(range(len(SP2)), key=lambda k: SP2[k])
for i in ans:
    print(i+1)
from sys import stdin, setrecursionlimit as lim

lim(100001)

n, m = map(int, raw_input().strip().split())
inp = stdin.readlines()

g1 = ([] for i in xrange(n + 1))
g2 = ([] for i in xrange(n + 1))
ans1 = [0 for i in xrange(n + 1)]
ans2 = [0 for i in xrange(n + 1)]

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

def dfs1(u):
    if ans1[u] != 0: return ans1[u]
    ret = 0
    for v in g1[u]:
        if ans1[v] != 0: ret = max(ret, ans1[v])
        else: ret = max(ret, dfs1(v))
    ret += 1
    ans1[u] = ret
    return ans1[u]

def dfs2(u):
    if ans2[u] != 0: return ans2[u]
    ret = 0
    for v in g2[u]:
        if ans2[v] != 0: ret = max(ret, ans2[v])
        else: ret = max(ret, dfs2(v))
    ret += 1
    ans2[u] = ret
    return ans2[u]

ans = 0
for i in xrange(1, n + 1):
    if ans1[i] == 0: ans = max(ans, dfs1(i))
for i in xrange(1, n + 1):
    if ans2[i] == 0: ans = max(ans, dfs2(i))

print ans - 1

### FIXED CODE ###

from sys import stdin, setrecursionlimit as lim

lim(100001)

n, m = map(int, raw_input().strip().split())
inp = stdin.readlines()

g1 = [[] for i in xrange(n + 1)]
g2 = [[] for i in xrange(n + 1)]
ans1 = [0 for i in xrange(n + 1)]
ans2 = [0 for i in xrange(n + 1)]

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

def dfs1(u):
    if ans1[u] != 0: return ans1[u]
    ret = 0
    for v in g1[u]:
        if ans1[v] != 0: ret = max(ret, ans1[v])
        else: ret = max(ret, dfs1(v))
    ret += 1
    ans1[u] = ret
    return ans1[u]

def dfs2(u):
    if ans2[u] != 0: return ans2[u]
    ret = 0
    for v in g2[u]:
        if ans2[v] != 0: ret = max(ret, ans2[v])
        else: ret = max(ret, dfs2(v))
    ret += 1
    ans2[u] = ret
    return ans2[u]

ans = 0
for i in xrange(1, n + 1):
    if ans1[i] == 0: ans = max(ans, dfs1(i))
for i in xrange(1, n + 1):
    if ans2[i] == 0: ans = max(ans, dfs2(i))

print ans - 1
import string

S = input()

if len(S) == 26: print(-1)
retS = ''
alphabetsStr = string.ascii_lowercase
alphabets = list(map(lambda x: x, string.ascii_lowercase))
found = False
lenS = len(S)
if S[0] == 'a':
    for i in range(len(S)):
        if S[i] != alphabets[i]:
            retS = string.ascii_lowercase[:i+1]
            found = True
            break
else:
    idx = alphabets.index(S[0])
    for i in range(1, idx+1):
        if S[i] != alphabets[i-1]:
            retS = S[:i] + alphabets[i-1]
            found = True
            break
    if not found:
        for i in range(idx+1, len(S)):
            if S[i] != alphabets[i]:
                retS = string.ascii_lowercase[:i+1]
                found = True
                break
    
if not found: retS = S + alphabets[len(S)]
print(retS)


    

### FIXED CODE ###

import string

S = input()
reversedS = ''.join(list(S)[::-1])
alphabets = list(string.ascii_lowercase)
lastWord = ''.join(alphabets[::-1])
cnt = [S.count(chr(ord('a')+i)) for i in range(26)]
if len(S) == 26:
    if S == lastWord: print(-1)
    else:
        found = False
        for i in range(len(reversedS)):
            s = reversedS[i]
            largeS = alphabets[ord(s)-ord('a')+1:]
            tailS = list(S)[26-i-1:]
            for lS in largeS:
                if lS in tailS:
                    print(S[:26-i-1]+lS)
                    found = True
                    break
            if found: break
else:
    for j in range(26):
        if cnt[j] == 0:
            S += chr(ord('a')+j)
            print(S)
            break
N = int(input())
W = list(map(int, input().split()))

m = 10**10
for i in range(1, W):
  m = min(m, abs(sum(W[:i]), sum(W[i:])))

print(m)

### FIXED CODE ###

N = int(input())
W = list(map(int, input().split()))

m = 10**10
for i in range(1, N):
  m = min(m, abs(sum(W[:i]) - sum(W[i:])))
                 
print(m)
A, B, C, D, E, F = map(int, input().split())

w = set()
for i in range(F // (100 * A) + 1):
    t = F - 100 * a
    for j in range(t // (100 * B) + 1):
        a = (A * i + B * j) * 100
        w.add(a)
w.remove(0)

s = set()
t = E * F // 100
for i in range(t // C + 1):
    for j in range(t // D + 1):
        b = C * i + D * j
        if b < t:
            s.add(b)

best_concentration = -1
best_a = -1
best_b = -1
for a in w:
    for b in sorted(s):
        if a + b > F:
            break
        if b > E * a // 100:
            break
        concentration = 100 * b / (a + b)
        if concentration > best_concentration:
            best_concentration = concentration
            best_a = a
            best_b = b
print(best_a + best_b, best_b)


### FIXED CODE ###

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

w = []
for i in range(F // (100 * A) + 1):
    for j in range(F // (100 * B) + 1):
        a = (A * i + B * j) * 100
        if a < F:
            w.append(a)

best_concentration = -1
best_a = -1
best_b = -1
for a in w:
    t = min(F - a, E * a // 100)
    for i in range(t // C + 1):
        for j in range(t // D + 1):
            b = C * i + D * j
            if a + b > F:
                continue
            if b > E * a // 100:
                continue
            if a + b == 0:
                continue
            concentration = 100 * b / (a + b)
            if concentration > best_concentration:
                best_concentration = concentration
                best_a = a
                best_b = b
print(best_a + best_b, best_b)
def prepare(n,arr):
    nodeArr = [[] for i in range(n)]
    for ar in arr:
        nodeArr[ar[0]-1].append([ar[1]-1,ar[2]])
        nodeArr[ar[1]-1].append([ar[0]-1,ar[2]])
    return nodeArr

def dfs(parent,currentNode,distance):

    if len(nodeArr[currentNode]) == 1:
        if currentNode != 0:
            # 末点
            res[currentNode] = distance
            return

    for next in nodeArr[currentNode]:
        nextNode = next[0]
        nextNodeDistance = next[1]
        if nextNode != parent:
            dfs(currentNode,nextNode,distance + nextNodeDistance)
    res[currentNode] = distance


n = int(input())

arr = []

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

nodeArr = prepare(n, arr)


if n == 1:
    print(1)
else:
    res = [-1 for i in range(n)]

    dfs(-1,0,0)

    result = [(re % 2) for re in res]

    for re in res:
        print(re % 2)



### FIXED CODE ###

import sys
sys.setrecursionlimit(20000000)
def prepare(n,arr):
    nodeArr = [[] for i in range(n)]
    for ar in arr:
        nodeArr[ar[0]-1].append([ar[1]-1,ar[2]])
        nodeArr[ar[1]-1].append([ar[0]-1,ar[2]])
    return nodeArr

def dfs(currentNode,distance):
    res[currentNode] = distance
    for next in nodeArr[currentNode]:
        nextNode = next[0]
        nextNodeDistance = next[1]
        if res[nextNode] == -1:
            dfs(nextNode,distance + nextNodeDistance)




n = int(input())

arr = []

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

nodeArr = prepare(n, arr)


if n == 1:
    print(1)
else:
    res = [-1 for i in range(n)]

    dfs(0,0)

    result = [(re % 2) for re in res]

    for re in res:
        print(re % 2)
import heapq
def SME():
    start = 0
    parameter = 0.99
    ANS = [None]*N
    [end,L] = [int(x) for x in input().split()]
    Whole = [int(x) for x in input().split()]
    A = []
    C = set([i for i in range(N)])
    D = set([])
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    D.add(idx)
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L:
            ANS[i] = min(Whole[:i+1])
        else :
            ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
n = int(input())
A = [0]*(10**5+5)
for i in range(n):
    a = int(input())
    A[a-1]+=1
    A[a-1]%=2
print(sum(A))


### FIXED CODE ###

n = int(input())
A = {}
for i in range(n):
    a = int(input())
    A[a] = A.get(a, 0)+1
    A[a] %= 2
s = 0
for v in A.values():
    s += v
print(s)
n = input()
a = map(int, raw_input().split())
color = [0 for _ in range(9)]
for item in a:
    i = item / 400
    i = max(i, 8)
    color[i] += 1

ans = 0
for num in color[0:8]:
    if num != 0:
        ans += 1

min_ans = max(ans, 1)
max_ans = ans + color[8]
max_ans = min(max_ans, 9)

print min_ans, max_ans


### FIXED CODE ###

n = input()
a = map(int, raw_input().split())
color = [0 for _ in range(9)]
for item in a:
    i = item / 400
    i = min(i, 8)
    color[i] += 1

ans = 0
for num in color[0:8]:
    if num != 0:
        ans += 1

min_ans = max(ans, 1)
max_ans = ans + color[8]
#max_ans = min(max_ans, 8)

print min_ans, max_ans