Harryxun/stf_run huggingface dataset:
#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 
import time
import sys

WARU = 1000000007

N, M = [ int(x) for x in input().split() ]
A = {}
for i in range(M):
    A[int(input())] = 1

ans = [None for i in range(N + 1)]
ans[0] = 1
ans[1] = 1 if not 1 in A else 0

def steps(n):
    if ans[n] is not None:
        return ans[n]
    if n in A:
        return 0
    #print ("{} : {}".format(n, steps(n - 1) + steps(n - 2)))
    ans[n] = (steps(n - 1) + steps(n - 2)) % WARU
    return ans[n]

#print(ans)
print(steps(N))


### FIXED CODE ###

#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 
import time
import sys

WARU = 1000000007

N, M = [ int(x) for x in input().split() ]
A = {}
for i in range(M):
    A[int(input())] = 1

ans = [None for i in range(N + 1)]
ans[0] = 1
ans[1] = 1
for a in A:
    ans[a] = 0

for i in range(N):
    n = i + 1
    if ans[n] is not None:
        continue
    ans[n] = (ans[n-2] + ans[n-1]) % WARU


print(ans[N])
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            num[max(0,j-a[j])]+=1
            num[min(n,j+a[j]+1)]-=1
        num5=0
        for j in range(n):
            num5+=num[j]
            ans[j]=num5
        a=ans
        if sum(ans)==n*n:
            break
    print(*a)


### FIXED CODE ###

s=input()
print(s[:3])
import sys
sys.setrecursionlimit(1000000)

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def combination(n,r,q):
    if r==1:
        return n%q

    return (n*combination(n-1,r-1,q)*modinv(r,q))%q

def _input():
    return list(map(int, input().split()))

def main():
    i=_input()
    x,y=i[0],i[1]
    if (2*y-x)%3==0 and (2*x-y)%3==0:
        n=(2*y-x)/3
        m=(2*x-y)/3
        print(int(combination(n+m,min(m,n),1000000007)))
    else:
        print(0)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def combination(n,r,q):
    if r==0:
        return 1

    return ((n*combination(n-1,r-1,q)%q)*modinv(r,q))%q

def _input():
    return list(map(int, input().split()))

def main():
    i=_input()
    x,y=i[0],i[1]
    if 2*y>=x and 2*x>=y and (2*y-x)%3==0 and (2*x-y)%3==0:
        n=(2*y-x)//3
        m=(2*x-y)//3
        print(int(combination(n+m,min(m,n),1000000007)))
    else:
        print(0)

if __name__ == "__main__":
    main()
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

l = input().rstrip().split(' ')

x = int(l[0])
y = int(l[1])

print(lcm(x, y))

### FIXED CODE ###

#最大公約数、最小公倍数
import fractions
a,b=map(int, input().split())
f=fractions.gcd(a,b)
f2=a*b//f
print(f2)
import collections
n=int(input())
ans=[]
s=["".join(sorted(input())) for _ in range(n)]
c=collections.Counter(s)
m=max(c.values())
for k,v in c.items:
  if v==m:
    ans.append(k)

print(sorted(k))




### FIXED CODE ###

import collections
n=int(input())
ans=[]
s=["".join(input()) for _ in range(n)]
c=collections.Counter(s)
m=max(c.values())
for k,v in c.items():
  if v==m:
    ans.append(k)

for i in sorted(ans):
  print(i)
def factorization(n):
    if n == 1:
        return []
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(i)
    if temp != 1:
        arr.append(temp)
    if not arr:
        arr.append(n)
    return arr


input_values = list(map(int, input().split()))
print(len(list(set(factorization(input_values[0])) & set(factorization(input_values[1])))) + 1)

### FIXED CODE ###

x = int(input())
y = 0.5 if x % 2 == 0 else  (x + 1) / 2 / x
print(y)
#abc122a

b=raw_input()
if b=='A':
 print 'T'
elif b=='C':
 print 'G'
elif b=='G':
 print 'C'
elif:
 print 'A'


### FIXED CODE ###

#abc122a

b=raw_input()
if b=='A':
 print 'T'
elif b=='C':
 print 'G'
elif b=='G':
 print 'C'
else:
 print 'A'
#文字列Tを突っ込むのはできるだけ最後の方が良い(残りは全てaにしないと辞書順で負けうる。)
#if 文字列が入らない→UNRESTORABLE
#if 文字列が入ったら全部aを入れられる。(ん？これってここまでやったら絶対に一番最初のやつになるのでは?)
#※すでに文字が入っていたら、文字列を入れずに全てaを突っ込む
#文字列をどうやって探すか。
#Tの長さと同じだけ?が連続している場所があるならいける
#というか一文字ずつみて(その文字or?ならオーケー)失敗したらindexを戻していけばいいので

def strProduct(S,T):
    Tindex = 0#Tのindex失敗するたびに0に戻る
    lt = len(T) #Tの文字列の長さ
    flag = False#Tの材料に ?がなければFalse
    reasonable = False#文字を作れるかどうか
    translateIndex = [] #SがTの文字列になる場所の初めの位置
    S.reverse()
    T.reverse()
    for si in range(len(S)):
        s = S[si]
        if s == T[Tindex] or s == "?":
            if Tindex == 0:#初めての一致
                translateIndex.append(si)
            if s == "?":#?をつかって文字列をつくる時と作らない時で異なるし、?を使わないのがあればそれを優先するべき
                flag = True
                if len(translateIndex) > 1:#すでに一つ完成している時はそっちを優先する
                    translateIndex.pop()#translateIndexには残らない
            Tindex += 1
            if Tindex == lt:#全てmatchingした時
                reasonable = True
                if not flag:#?を使わないなら優先的にそれを使う
                    break
                #初期化して次のを探す
                Tindex = 0
                flag = False
        else: #一回でも失敗すれば初期化
            Tindex = 0
            flag = False
            #translateIndexはあまり関係ない
    if flag:#?を使わないとできないなら変更します。
        for j in range(translateIndex[len(translateIndex)-1],translateIndex[len(translateIndex)-1]+lt):
            S[j] = T[j-translateIndex[len(translateIndex)-1]]
    S.reverse()
    #T.reverse()
    if not reasonable:
        return "UNRESTORABLE"
    else:
        for si in range(len(S)):
            if S[si] == "?":
                S[si] = "a"
        modifiedS = ''.join(S)
        return modifiedS

S = list(input())
T = list(input())
#print(S)
#print(T)
print(strProduct(S,T))


### FIXED CODE ###

sp = input()
t = input()
len_t = len(t)
len_s = len(sp)
cand = []
part_start = -1

for i in range(len_s - len_t + 1):
    num = 0
    for j in range(len_t):
        if (sp[i + j] == '?' or sp[i + j] == t[j]):
            num += 1

    if (num == len_t):
        part_start = i

if part_start != -1:
    # 部分文字列は最後にあったほうがいい?はaで最小化できる可能性があり、文字列の先頭に近い部分にそれらがあったほうがよい
    ans = sp[:part_start] + t + sp[part_start + len_t:]
    ans = ans.replace('?', 'a')
    print(ans)
else:
    print('UNRESTORABLE')
import sys
import numpy as np


def count_water(np_arr):
  least = min(np_arr)
  div_p = np.where(np_arr == least)[0]
  np_arr -= least
  return least + count_water(np_arr[:div_p]) + count_water(np_arr[div_p + 1:])


def main():
  readline = sys.stdin.readline
  
  n = int(readline().rstirp())
  h = np.array(tuple(int(_) for _ in readline().rstrip().split()))
  
  print(count_water(h))

 
if __name__ == "__main__":
  main()


### FIXED CODE ###

import sys
import numpy as np


def count_water(np_arr):
  if not np_arr.any():
    return 0
  least = min(np_arr)
  div_p = np.where(np_arr == least)[0][0]
  np_arr -= least
  return least + count_water(np_arr[:div_p]) + count_water(np_arr[div_p + 1:])


def main():
  readline = sys.stdin.readline
  
  n = int(readline().rstrip())
  h = np.array(tuple(int(_) for _ in readline().rstrip().split()))
  
  print(count_water(h))

 
if __name__ == "__main__":
  main()
S = input()

print("Yes" if set(S)=("a", "b", "c") else "No")


### FIXED CODE ###


S = input()

print("Yes" if set(S)=={"a", "b", "c"} else "No")
N = int(input())
ABC = [tuple(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
XY = [tuple(map(int, input().split())) for i in range(Q)]

tree = [[] for i in range(N+1)]   
depth = [None] * (N+1)

for abc in ABC:
    tree[abc[0]].append((abc[1],abc[2]))
    tree[abc[1]].append((abc[0],abc[2]))
    
def DFS(v, p, d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
            
DFS(K, 0, 0)

for x,y in XY:
    print(depth[x] + depth[y])
    

### FIXED CODE ###

import sys;sys.setrecursionlimit(int(1e7))

N = int(input())
ABC = [tuple(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
XY = [tuple(map(int, input().split())) for i in range(Q)]

tree = [[] for i in range(N+1)]   
depth = [None] * (N+1)

for abc in ABC:
    tree[abc[0]].append((abc[1],abc[2]))
    tree[abc[1]].append((abc[0],abc[2]))
    
def DFS(v, p, d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
            
DFS(K, 0, 0)

for x,y in XY:
    print(depth[x] + depth[y])
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    n,a,b = map(int,input().split())

    if a==b:
        print(0)
    elif a==1:
        print(str(b))
    elif b==1:
        print(str(a))
    else:
        if abs(a-b)%2==0:
            ans=abs(a-b)//2
        else:
            if n-min(a,b)>max(a,b)-1:
                ans=max(a,b)-1
            else:
                ans=n-min(a,b)
    print(ans)

if __name__=="__main__":
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    n,a,b = map(int,input().split())
    ans=0
    if (b-a) % 2 == 0:
        print((b-a) // 2)
    else:
        print((b-a)//2 + min(a-1,n-b) + 1)

if __name__=="__main__":
    main()
input = sys.stdin.readline

from functools import reduce
from fractions import gcd
import numpy as np

MOD = 10**9+7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)


def main():
    N = int(input())
    a = [int(i) for i in input().split()]
    A = np.array(a)

    lcm = reduce(lcm_base, a, 1)
    B = lcm // A

    print(np.sum(B) % MOD)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from functools import reduce
from fractions import gcd

MOD = 10**9+7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def main():
    N = int(input())
    a = [int(i) for i in input().split()]

    lcm = reduce(lcm_base, a, 1)
    
    ans = 0
    for i in a:
        ans += lcm // i

    print(ans % MOD)


if __name__ == "__main__":
    main()
from functools import lru_cache
#@lru_cache(maxsize=3000)
@memoize
def burger(str_b,level):
  if(level == 0):
    return str_b + 'p'
  str_b += 'B'
  str_b = burger(str_b,level-1)
  str_b += 'p'
  str_b = burger(str_b,level-1)
  str_b += 'B'
  return str_b


str_b = ''
N,X = map(int,input().split())
str_b = burger(str_b,N)
b_list = list(str_b)
eat_list = b_list[::-1]
eat_list = b_list[0:X]
print(eat_list.count('p'))

### FIXED CODE ###

n,x = map(int,input().split())
a,p = [1],[1]
for i in range(n):
  a.append(2*a[i]+3)
  p.append(2*p[i]+1)

def f(N,X):
  if N==0:
    return 0 if X<=0 else 1
  elif X <= 1+a[N-1]:
    return f(N-1,X-1)
  else:
    return p[N-1]+1+f(N-1,X-2-a[N-1])
print(f(n,x))
N = int(input())
print(min(sum(*map(int,input().split()))))

### FIXED CODE ###

N = int(input())
print(min([sum(list(map(int,input().split()))) for j in range(N)]))
import sys


def main():
    one_try = int(sys.argv[1])
    money = int(sys.argv[2])
    count = int(sys.argv[3])
    n = 0
    while(True):
        if money >= one_try:
            money = money - one_try
            n = n + 1
        else:
            break
        if n == count:
            break
    print(n)


if __name__ == '__main__':
    main()
    

### FIXED CODE ###

import sys


def main():
    lines = sys.stdin.readlines()[0].split(' ')
    one_try = int(lines[0])
    money = int(lines[1])
    count = int(lines[2])
    n = 0
    while(True):
        if money >= one_try:
            money = money - one_try
            n = n + 1
        else:
            break
        if n == count:
            break
    print(n)


if __name__ == '__main__':
    main()
N = input()
X = list(map(int, input().split()))
for a in X:
    sum = sum + a
C = sum/N
for b in X:
    ans = (b-C)**2

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
sum = 0
all = True
for a in X:
    sum = sum + a
C = int(sum / N + 0.5)
ans = 0
for b in X:
    ans = ans + (b-C)**2
print(ans)
week = {1: "Thursday", 2: "Friday", 3: "Saturday", 4: "Sunday", 5: "Monday", 6: "Tuesday", 7: "Wednesday"}
month = {1: 0, 2: 31, 3: 60, 4: 91, 5: 121, 6: 152, 7: 182, 8: 213, 9: 244, 10: 274, 11: 305, 12: 335}
m, d = map(int, input().split())
while m:
    days = month[m] + d
    print(week[days % 7])
    m, d = map(int, input().split())

### FIXED CODE ###

while True:
    m, d = map(int, input().split())
    if m == d == 0:
        break
    dim = {1: 0, 2: 31, 3: 60, 4: 91, 5: 121, 6: 152, 7: 182, 8: 213, 9: 244, 10: 274, 11: 305, 12: 335}
    ds = dim[m] + d -1
    print({0:'Thursday', 1:'Friday', 2:'Saturday', 3:'Sunday', 4:'Monday', 5:'Tuesday', 6:'Wednesday'}[ds % 7])
import math

T = int(input())

for _ in range(T):
    A, B, C, D = map(int, input().split())
    if (A < B) or (D < B):
        print('No')
        continue
    elif (C+1 >= B):
        print('Yes')
        continue
    else:
        s_res = A % B
        s_k = int((C + 1 - s_res - 0.1) // B + 1)
        X = math.gcd(B, (D%B))
        if X == 1:
            print('No')
            continue
        else:
            s_0 = s_k * B + s_res
            if (s_0 - (C+1)) % X > (B-C-2):
                print('Yes')
            else:
                print('No')



### FIXED CODE ###


def gcd(a, b):
	while b:
		a, b = b, a % b
	return a


T = int(input())

for _ in range(T):
    A, B, C, D = map(int, input().split())
    if (A < B) or (D < B):
        print('No')
        continue
    elif (C+1 >= B):
        print('Yes')
        continue
    else:
        s_res = A % B
        s_k = int((C + 1 - s_res - 0.1) // B + 1)
        X = gcd(B, (D%B))
        if X == 1:
            print('No')
            continue
        else:
            s_0 = s_k * B + s_res
            if (s_0 - (C+1)) % X > (B-C-2):
                print('Yes')
            else:
                print('No')
N, Q = map(int, input().split())
S = input()

A = []
for i in range(Q):
    l, r = map(int, input().split())
    A.append(S[l - 1 : r])
    
for a in A:
    print(a.count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

dp = [0] * (N + 1)
for i in range(N):
    if S[i : i + 2] == 'AC':
        dp[i + 1] += 1
        
for i in range(1, N + 1):
    dp[i] += dp[i - 1]
    
for i in range(Q):
    l, r = map(int, input().split())
    print(dp[r - 1] - dp[l - 1])
import fractions
N, X = map(int, input().split())
x = map(int, input().split())
r = abs(X-next(x))
for i in x:
    r = fractions.gcd(r, i-X))
print(r)

### FIXED CODE ###

import fractions
N, X = map(int, input().split())
x = map(int, input().split())
r = abs(next(x)-X)
for i in x:
    r = fractions.gcd(r, abs(i-X))
print(r)
print(chr(ord(input() + 1)))

### FIXED CODE ###

print(chr(ord(input()) + 1))
g=[0,2,0,1,0,1,0,0,1,0,1,0]
a,b=map(int,input().split())
print('Yes' if g[a]==g[b] else 'No')

### FIXED CODE ###

g=[0,2,0,1,0,1,0,0,1,0,1,0]
a,b=map(int,input().split())
print('Yes' if g[a-1]==g[b-1] else 'No')
N = int(input())
A = [int(input()) for _ in range(N)]

MAX_1 = max(A)
MAX_2 = sorted(set(A))[-2]

for i in range(N):
    if A[i] == MAX_1:
        print(MAX_2)
    else:
        print(MAX_1)

### FIXED CODE ###

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

MAX_1 = max(A)
MAX_2 = sorted(A)[-2]

for i in range(N):
    if A[i] == MAX_1:
        print(MAX_2)
    else:
        print(MAX_1)
def resolve():
    str = input()
    if re.match('(hi)+', str):
        print("Yes")
    else:
        print("No")

resolve()

### FIXED CODE ###

import re

def resolve():
    str = input()
    if re.match('^(hi)+$', str):
        print("Yes")
    else:
        print("No")
        
resolve()
import numpy as np
h,w,m=map(int, input().split())
a = np.zeros((h,w))
ans=0

for i in range(m):
    x,y=map(int, input().split())
    a[x-1,y-1]=1
    
c = a.sum(axis=0)
r = a.sum(axis=1)
cm = max(c)
rm = max(r)
ci = [i for i, x in enumerate(c) if x == cm]
ri = [i for i, x in enumerate(r) if x == rm]
ans = cm + rm

#print(a,c,r,ci,ri)

for i in ri:
    for j in ci:
        if a[i,j]==0:
            print(int(ans))
            exit()

print(int(ans)-1)

### FIXED CODE ###

h,w,m=map(int, input().split())
r = [0]*max(h,w)
c = [0]*max(h,w)
l=[]

for i in range(m):
    x,y=map(int, input().split())
    r[x-1]+=1
    c[y-1]+=1
    l.append([x,y])

cm = max(c)
rm = max(r)
ci = [i for i, x in enumerate(c) if x == cm]
ri = [i for i, x in enumerate(r) if x == rm]
ans = cm + rm

cnt = 0
#print(l,ci,ri)
for i in range(m):
    if r[l[i][0]-1] == rm and c[l[i][1]-1] ==cm:
        cnt += 1

if cnt == len(ci)*len(ri):
    print(int(ans)-1)
else:
    print(int(ans))
n=int(input())
a=list(map(int,input().split()))
b=list(map(int, input().split()))
ans = 0
        for i in range(n):
                        ans = max(ans,sum(a[:i+1])+sum(b[i:n]))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(map(int, input().split()))
ans = 0
for i in range(n):
        ans = max(ans,sum(a[:i+1])+sum(b[i:n]))
print(ans)
from scipy.misc import comb
from collections import Counter

N=int(input())
A=list(map(int,input().split() ))
B=[-1]*N   #メモ化。iの時の方法の総数

for i,item in enumerate(A):
  if B[item-1]>-1:
    #print(i,item,"は計算済み！")
    #print(i,B[item-1],"done")
    print(B[item-1])
  else:
    C=A[0:i]+A[i+1:] #仮で作るリスト
    cnt = Counter(C)
    D=dict(cnt)
    E=[]
    for item2 in D:
      if D[item2]>=2:
        E.append(D[item2])
    #print(i,E)
    opt=0
    for item3 in E:
      opt += comb(item3,2,exact=True)
    B[item-1]=opt
    #print(i,opt)
    print(opt)
    #print(i,E,opt)
    #print(C,cnt)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split() ))
from collections import Counter
d=dict(Counter(A))
#print(d)
cnt=0
for item in d:
    cnt += (d[item])*(d[item]-1)//2

#print("cnt",cnt)
   
for num in A:
    new = max(0, (d[num]-1)*(d[num]-2)//2)
    print(cnt- d[num]*(d[num]-1)//2 + new)
n, k = map(int, input().split())

d = int(input())

num = [int(input()) for _ in range(n)]

print(n - d)

### FIXED CODE ###

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

ans = []

for i in range(k*2):
  x = input().split()
  if 1 == i % 2:
    for j in range(len(x)):
      if int(x[j]) not in ans:
        ans.append(int(x[j]))

print(n - len(ans))
w = 0
codea = "a".encode()
for x in input():
  w ^= 1 << (x.encode() - codea)
print("No" if w!=0 else "Yes")


### FIXED CODE ###

w = 0
codea = "a".encode()[0]
for x in input():
  w ^= 1 << (x.encode()[0] - codea)
print("No" if w!=0 else "Yes")
N,K = list(map(str, input().split()))
if N % K != 0:
  print(1)
else:
  print(0)

### FIXED CODE ###

N,K = map(int, input().split())
if N % K == 0:
  print(0)
else:
  print(1)
while True:
    (m, f, r) = [int(i) for i in input().split()]
    if m == f == r == -1:
        break

    total = m + f
    if m == -1 or f == -1 or total < 30:
        print('F')
    elif total < 50 and r < 5-:
        print('D')
    elif total < 65:
        print('C')
    elif total < 85:
        print('B')
    else:
        print('A')

### FIXED CODE ###

while True:
    (m, f, r) = [int(i) for i in input().split()]
    if m == f == r == -1:
        break

    total = m + f
    if m == -1 or f == -1 or total < 30:
        print('F')
    elif total < 50 and r < 50:
        print('D')
    elif total < 65:
        print('C')
    elif total < 80:
        print('B')
    else:
        print('A')
wa

### FIXED CODE ###

# 解説AC
def solve():
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    basis=[]
    for i in range(n-1,-1,-1):
      	# 基底を求める
        for e in basis:
            a[i]=min(a[i],a[i]^e)
        if a[i]:
            if s[i]=="0":
                basis.append(a[i])
            else:
                print(1)
                return
    print(0)

t=int(input())
for _ in range(t):
    solve()
n = int(input())
boss_list = list(map(int, input().split(' ')))

# for i in range(n):
#     print(boss_list.count(i + 1))

import collections
c = collections.Counter(boss_list)

for i in range(n):
    print(boss_list[i + 1])

### FIXED CODE ###

n = int(input())
boss_list = list(map(int, input().split(' ')))

# for i in range(n):
#     print(boss_list.count(i + 1))

import collections
c = collections.Counter(boss_list)

for i in range(n):
    print(c[i + 1])
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
M = {}
K = int(input())
for i in range(K):
    V, P = map(int, input().split())
    M[V-1] = P
memo = [0]*N
def dfs(v, p, x, y):
    if v in M:
        x = y = M[v]
    x0 = x; y0 = y
    for w in G[v]:
        if p == w:
            continue
        s, t = dfs(w, v, x-1, y+1)
        x0 = max(x0, s-1)
        y0 = min(y0, t+1)
    for w in G[v]:
        if p == w:
            continue
        dfs(w, v, x0-1, y0+1)
    memo[v] = x0, y0
    return x0, y0
INF = 10**18
dfs(list(M.keys())[0], -1, -INF, INF)
ok = 1
for i in range(N):
    x, y = memo[i]
    if not x <= y:
        ok = 0
if ok:
    print('Yes')
    print(*map(lambda x: x[1], memo), sep='\n')
else:
    print('No')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
M = {}
K = int(input())
for i in range(K):
    V, P = map(int, input().split())
    M[V-1] = P
memo = [0]*N
def dfs(v, p, x, y):
    if v in M:
        x = y = M[v]
    x0 = x; y0 = y
    for w in G[v]:
        if p == w:
            continue
        s, t = dfs(w, v, x-1, y+1)
        x0 = max(x0, s-1); y0 = min(y0, t+1)
    memo[v] = x0, y0
    return x0, y0
def dfs1(v, p, x, y, c):
    if v in M:
        x = y = M[v]
        if c != (M[v] % 2):
            return 0
    x0, y0 = memo[v]
    x = max(x, x0); y = min(y, y0)
    for w in G[v]:
        if p == w:
            continue
        if not dfs1(w, v, x-1, y+1, c^1):
            return 0
    memo[v] = x, y
    return 1

INF = 10**18
f = list(M.keys())[0]
dfs(f, -1, -INF, INF)
ok = dfs1(f, -1, -INF, INF, M[f]%2)
for i in range(N):
    x, y = memo[i]
    if not x <= y:
        ok = 0
if ok:
    print('Yes')
    print(*map(lambda x: x[1], memo), sep='\n')
else:
    print('No')
N, M = map(int, input().split())
SC = [list(map(int, input().split())) for _ in range(M)]
ans = []
SC = sorted(SC)

for x, item in enumerate(SC):
    if len(ans) + 1 < item[0]:
        if len(ans) == 0:
            ans.append(1)
        for y in range(item[0] -len(ans) - 1):
            ans.append(0)
    if len(ans) + 1 == item[0]:
        ans.append(item[1])
    elif len(ans) == item[0]:
        continue

if len(ans) < N:
    for x in range(N - len(ans)):
        ans.append(0)

if ans(0) == 0 and len(ans) != 0:
    print(-1)
else:
    ans = map(str, ans)
    print("".join(ans))

### FIXED CODE ###

N = int(input())

print(-(-N // 2))