Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import heapq;

n, u, v = [int(v) for v in input().split()]

vert = []

for i in range(n):
    vert.append([])

for i in range(n - 1):
    a, b = [int(v) - 1 for v in input().split()]
    vert[a].append(b)
    vert[b].append(a)

taka = u-1
aoki = v-1

q = [(0, aoki)]
aoki_dist = [-1] * n
closed = 0

index = 0
while index < len(q):
    c0, i = q[index]
    aoki_dist[i] = c0
    c = c0 + 1
    for l in vert[i]:
        if closed & (1 << l) != 0:
            continue
        closed |= (1 << i)
        q.append((c, l))
    index += 1

q = [(0, taka)]
closed = (1 << taka)
max_dist = aoki_dist[taka]

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if closed & (1 << l) != 0:
            continue
        closed |= (1 << l)
        if c >= aoki_dist[l]:
            continue
        if max_dist < aoki_dist[l]:
            max_dist = aoki_dist[l]
        q.append((c, l))

    index += 1

print(max_dist - 1)


### FIXED CODE ###

import heapq;

n, u, v = [int(v) for v in input().split()]

vert = []

for i in range(n):
    vert.append([])

for i in range(n - 1):
    a, b = [int(v) - 1 for v in input().split()]
    vert[a].append(b)
    vert[b].append(a)

taka = u-1
aoki = v-1

if taka == aoki:
    print(0)
    exit()

def bfs(begin):
    q = [(0, begin)]
    dist = [-1] * n
    dist[begin] = 0

    index = 0
    while index < len(q):
        c0, i = q[index]
        c = c0 + 1
        for l in vert[i]:
            if dist[l] >= 0:
                continue
            dist[l] = c
            q.append((c, l))
        index += 1
    return dist

aoki_dist = bfs(aoki)
taka_dist = bfs(taka)

ans = 0
for i in range(n):
    if taka_dist[i] < aoki_dist[i]:
        ans = max(ans, aoki_dist[i] - 1)

print(ans)
### BUGGY CODE ###

from collections import Counter

N = int(input())

A = []
for i in range(N):
    a = input()
    a_counter = Counter(a).most_common()
    a_counter.sort(key = lambda x: x[1])
    a_counter.sort(key = lambda x: x[0])
    A.append(a_counter)
    
cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i] == A[j]:
            cnt += 1
            
print(cnt)

### FIXED CODE ###

N = int(input())
 
D = {}
for i in range(N):
    s = ''.join(sorted(input()))
    D.setdefault(s, 0)
    D[s] += 1
    
ans = 0
for v in D.values():
    if v > 1:
        for i in range(v):
            ans += i
    
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop, heapify
import numpy as np
N, M = map(int,input().split())
A = list(map(int,input().split()))
A = np.array(A)
A = -A
A = list(A)
for _ in range(M):
    heapify(A)
    s = heappop(A)
    heappush(A, -(-s // 2))
A = np.array(A)
print(-int(np.sum(A)))

### FIXED CODE ###

from heapq import heappush, heappop, heapify
import numpy as np
N, M = map(int,input().split())
A = list(map(int,input().split()))
A = np.array(A)
A = -A
A = list(A)
heapify(A)
for _ in range(M):    
    s = heappop(A)
    heappush(A, -(-s // 2))
A = np.array(A)
print(-int(np.sum(A)))
### BUGGY CODE ###

n, k = map(int,input().split())
l = list(map(int,input().split()))
#print(l)

x =0
y = 0
for i in range(n-k+1):
    if x < max(sum(l[i:i+k]),x):
        x = max(sum(l[i:i+k]),x)
        y = i
#print(x,y)

z = 0
for j in range(y,y+k):
    z += (l[j]+1)/2

print(z)





### FIXED CODE ###

from itertools import accumulate

n, k = map(int,input().split())
l = list(map(int,input().split()))
#print(l)

p = [0] + list(accumulate(l))

#print(p)

q = []
for i in range(n-k+1):
    q.append((p[i+k] - p[i] + k)/2)

print(max(q))
### BUGGY CODE ###

from sys import stdin
n,k = map(int,stdin.readline().split())
p = list(map(int,stdin.readline().split()))
c = list(map(int,stdin.readline().split()))
 
ans = -float("inf")
def helper(index):
    visited  = {index}
    looplen = 1
    looptotal = c[index]
    while p[index]-1 not in visited:
        nextindex = p[index] - 1
        looplen += 1
        looptotal += c[nextindex]
        visited.add(nextindex)
        index = nextindex
    return (looplen,looptotal)
 
for i in range(n):
    looplen,looptotal = helper(i)
    if looptotal >= 0:
        cur = looptotal*((k//looplen)-1) if k >= looplen else 0
        remain = looplen + (k%looplen) if k >= looplen else k
    else:
        cur = 0
        remain = looplen
    curmax = -float("inf")
    curindex = i
    for _ in range(remain):
        nextindex = p[curindex]-1
        cur += c[nextindex]
        curmax = max(curmax,cur)
        curindex = nextindex
    ans = max(ans,curmax)
print(ans)

### FIXED CODE ###

from sys import stdin
n,k = map(int,stdin.readline().split())
p = list(map(int,stdin.readline().split()))
c = list(map(int,stdin.readline().split()))

ans = -float("inf")
def helper(index):
    visited  = {index}
    looplen = 1
    looptotal = c[index]
    while p[index]-1 not in visited:
        nextindex = p[index] - 1
        looplen += 1
        looptotal += c[nextindex]
        visited.add(nextindex)
        index = nextindex
    return (looplen,looptotal)

for i in range(n):
    looplen,looptotal = helper(i)
    if looptotal >= 0:
        cur = looptotal*((k//looplen)-1) if k >= looplen else 0
        remain = looplen + (k%looplen) if k >= looplen else k
    else:
        cur = 0
        remain = looplen
    curmax = -float("inf")
    curindex = i
    for _ in range(remain):
        nextindex = p[curindex]-1
        cur += c[nextindex]
        curmax = max(curmax,cur)
        curindex = nextindex
    ans = max(ans,curmax)
print(ans)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

# N: 処理する区間の長さ

INF = 10**9 + 1
N = q
LV = (N-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
import bisect



for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, x)

for i, j in enumerate(d):
    res = query(i, i + 1)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)
    



### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        print(-1)
        #ans.append(-1)
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            print(x)
            #ans.append(x)
            flag = 0
            break
    if flag:
        print(-1)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(0, M):
    B, C = map(int, input().split())
    A += [C]*B
A.sort(reverse=True)
print(sum(A[0:N]))

### FIXED CODE ###

#!/usr/bin/env python3
import heapq

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

bc = sorted(bc, key=lambda x: x[1], reverse=True)
# print(bc)

heapq.heapify(a)
for b, c in bc:
    for i in range(b):
        num = heapq.heappop(a)
        if num < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, num)
            break
# print(a)
print(sum(a))
### BUGGY CODE ###

'''
☆長さnの数列Aの中央値がxであるとは
１．x以上の要素が (n + 1)// 2 個以上
２．そのようなxの中で最小
ということ。
'''

class BIT:
    def __init__(self, n):
        self.bit = [0] * (n+1)

    def sum(self, i):
        '''
        :param i: 
        :return: bit[i]までの和
        '''
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        '''
        :param i:
        :param x:
        :return: bit[i]にxを加える
        '''
        while i < len(self.bit):
            self.bit[i] += x
            i += i & -i

import numpy as np

def median(L):
    n = len(L)
    L.sort()
    return L[n // 2]

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

def ans_bigger(X):
    '''
    答えがX以上かどうかを判定
    つまり、区間[l. r]のうち中央値がX以上であるものが ((N+1) * N /2 + 1 ) //2 個以上かを判定
    [l, r]の中央値がX以上 =
    '''
    a_X = np.array([1 if a[i] >= X else -1 for i in range(N)]) #1, -1に変換
    cum = np.hstack(([0], np.cumsum(a_X))) #累積和を取る
    min_cum = min(cum)
    cum -= min_cum - 1 #BITを使うために全部0以上に

    b = BIT(max(cum) + 1)
    ans = 0
    for j in range(N + 1):
        ans += b.sum(cum[j])
        b.add(cum[j], 1)
    if ans >= ((N+1) * N /2 + 1 ) //2:
        return True
    else:
        return False

l = min(a)
r = max(a) + 1
#区間[l, r)を2分探索
while r > l + 1:
    if ans_bigger((l + r) // 2):
        l = (l + r) // 2
    else:
        r = (l + r) // 2
print(l)

### FIXED CODE ###

'''
☆長さnの数列Aの中央値がxであるとは
１．x以上の要素が (n + 1)// 2 個以上
２．そのようなxの中で最小
ということ。
'''

class BIT:
    def __init__(self, n):
        self.bit = [0] * (n+1)

    def sum(self, i):
        '''
        :param i: 
        :return: bit[i]までの和
        '''
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        '''
        :param i:
        :param x:
        :return: bit[i]にxを加える
        '''

        while i < len(self.bit):
            self.bit[i] += x
            i += i & -i

'''
def median(L):
    n = len(L)
    L.sort()
    return L[n // 2]
'''

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

def ans_bigger(X):
    '''
    答えがX以上かどうかを判定
    つまり、区間[l. r]のうち中央値がX以上であるものが ((N+1) * N /2 + 1 ) //2 個以上かを判定
    [l, r]の中央値がX以上 =
    '''
    a_X = [1 if a[i] >= X else -1 for i in range(N)]#1, -1に変換
    cum = [N]
    for i in range(N):
        cum.append(cum[i] + a_X[i]) #累積和を取るが、BITを使うため全部0以上に（初項N）
    b = BIT(2 * N + 1)
    ans = 0
    for j in range(N + 1):
        ans += b.sum(cum[j])
        b.add(cum[j], 1)
    if ans >= ((N+1) * N /2 + 1 ) //2:
        return True
    else:
        return False

l = min(a)
r = max(a) + 1
#区間[l, r)を2分探索
while r > l + 1:
    if ans_bigger((l + r) // 2):
        l = (l + r) // 2
    else:
        r = (l + r) // 2
print(l)
### BUGGY CODE ###

n = int(input())
s = input()

mx = 0
for i in range(1, n):
    t = 0
    for j in range(n - i):
        t = t + 1 if s[j] == s[j + i] else 0
        mx = max(mx, min(i, t))

print(mx)

### FIXED CODE ###

n = int(input())
s = input()

mx = 0
for i in range(1, n):
    t = 0
    for j in range(n - i):
        t = t + 1 if s[j] == s[j + i] else 0
        mx = max(mx, min(i, t))

print(mx)
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
t = 0
d = {t:0}
for i in s :
	t ^= 1 << (ord(i)-ord('a'))
	for j in range(26) :
		if (t^(1<<j)) in d :
			d[t] = min(d[t] if t in d else int(1e9),d[t^(1<<j)]+1)
print(d[t] if d[t] else 1)


### FIXED CODE ###

#!/usr/bin/env python3
s = input()
t = 0
d = {t:0}
for i in (ord(x)-ord('a') for x in s) :
	t ^= 1 << i
	d[t] = min(d[t] if t in d else 1000000, min((d[t^(1<<j)] for j in range(26) if t^(1<<j) in d))+1)
print(d[t] if d[t] else 1)
### BUGGY CODE ###

n = int(input())
nxt_btn = {i: int(input()) for i in range(1, n + 1)}

num = 0
crr_btn = 1
while True:
    num += 1
    if nxt_btn[crr_btn] == 1:
        num = -1
        break
    if nxt_btn[crr_btn] == 2:
        break
    crr_btn = nxt_btn[crr_btn]
print(num)


### FIXED CODE ###

n = int(input())
nxt_btn = {i: int(input()) for i in range(1, n + 1)}

num = -1
crr_btn = 1
for i in range(1, n + 1):
    if nxt_btn[crr_btn] == 2:
        num = i
        break
    crr_btn = nxt_btn[crr_btn]
print(num)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

bc.sort(key = lambda x:x[1], reverse = True)

d = []
loop = 0

while True:
        for b, c in bc:
                d.extend([c] * b)
                loop += 1
        if len(d) > n:
                break
        elif loop == m:
                break

a.extend(d)
a.sort(reverse = True)

print(sum(a[0:n]))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

bc.sort(key = lambda x:x[1], reverse = True)

a.sort()

a_count = 0
for b, c in bc:
        if c > a[a_count]:
                for i in range(b):
                        if c > a[a_count]:
                                a[a_count] = c
                                a_count += 1    
                        else:
                                break
                        if a_count == n:
                                        break

        else:
                break
        if a_count == n:
                break        

print(sum(a))
### BUGGY CODE ###

import bisect
s = input()
K = int(input())
substring = []
for i in range(len(s)):
    for j in range(i, len(s)):
        if len(substring) <= 5:
            substring.append(s[i: j + 1])
            substring = list(set(substring))
            substring.sort()
        elif substring[-1] > s[i: j + 1] and not s[i:j+1] in substring :
            bisect.insort_left(substring, s[i: j + 1])

                
print(substring[K-1])

### FIXED CODE ###

s = input()
K = int(input())
substring = []
for i in range(len(s)):
    for j in range(i, i+5):
        substring.append(s[i: j + 1])
substring = list(set(substring))
substring.sort()                
print(substring[K-1])
### BUGGY CODE ###

from collections import deque

H,W=map(int, raw_input().split())
A=[ list(raw_input())  for i in range(H) ]


def bfs(h,w):
	V=[ [ 0 for j in range(W) ] for i in range(W)  ]
	K=[ [ 0 for j in range(W) ] for i in range(W)  ]  #Kyori
	D=[ (-1,0),(1,0),(0,1),(0,-1)]

	q=deque()
	V[h][w]=1
	q.append( (h,w) )
	while q:
	#for i in range(5):
		h, w=q.popleft()	# newh , neww
		for dx,dy in D:
			if 0<=h+dx<H and 0<=w+dy<W:
				if A[h+dx][w+dy]=="#":
					return K[h][w]+1
				if A[h+dx][w+dy]=="." and V[h+dx][w+dy]==0:
					V[h+dx][w+dy]=1
					K[h+dx][w+dy]=K[h][w]+1
					q.append( (h+dx,w+dy) )	

ans=0	
for i in range(H):
	for j in range(W):
		ans=max(ans, bfs(i,j) )

print ans


### FIXED CODE ###

import sys
from collections import deque

H,W=map(int, raw_input().split())
A=[ list( sys.stdin.readline().strip())  for i in range(H) ]


D=[ (-1,0),(1,0),(0,1),(0,-1) ]
K=[ [ float("inf") for j in range(W) ] for i in range(H)  ]  #Kyori

q=deque()

for i in range(H):
	for j in range(W):
		if A[i][j]=="#":
			q.append( (i,j) )
			K[i][j]=0


while q:
	h,w=q.popleft()
	for dx,dy in D:
		if 0<=h+dx<H and 0<=w+dy<W and K[h+dx][w+dy]>K[h][w]+1:
				K[h+dx][w+dy]=K[h][w]+1
				q.append( (h+dx,w+dy) )	

ans=0
for x in K:
	ans=max(ans, max(x) )
print ans
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
h2 = sorted(h)

ans = 0
for i in range(n-k):
  ans += h2[0]
  del h2[0]
  
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
h2 = sorted(h)

if n<k:
  print(0)
else:
  print(sum(h2[0:n-k]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

N, W = [int(item) for item in input().split()]
item = np.array([[int(item) for item in input().split()] for _ in range(N)])


dp = np.full((N+1, 10**5 + 1), 10**12+1)
dp[0][0] = 0

for i in range(N):
    for j in range(10**5 + 1):
        w, v = item[i]
        if j >= v:
            dp[i+1][j] = min(dp[i][j], dp[i][j - v] + w)
        else:
            dp[i+1][j] = dp[i][j]

print(np.where(dp[N] <= W)[0][-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

N, W = [int(item) for item in input().split()]
item = np.array([[int(item) for item in input().split()] for _ in range(N)])


dp = np.full((N+1, 10**5 + 1), 10**12+1)
dp[0][0] = 0

for i in range(N):
    dp[i+1] = dp[i]
    w, v = item[i]
    np.minimum(dp[i][v:], dp[i][:-v] + w, out=dp[i+1][v:])

print(np.where(dp[N] <= W)[0][-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
li = [list(map(int, input().split())) for i in range(Q)]
cnt = [0]*N
for i in range(N):
	cnt[i] = S[0:i+1].count("AC")
for i in range(Q):
	print(S[li[i][0]-1:li[i][1]].count("AC"))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cnt = [0]*(N)
for i in range(1,N):
	cnt[i] = cnt[i-1] + (1 if S[i-1:i+1] == "AC" else 0)
for i in range(Q):
	l, r = map(int, input().split())
	print(cnt[r-1] - cnt[l-1])
### BUGGY CODE ###

n,m = map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
absort=sorted(ab,key=lambda x:(x[0],-x[1]))

ans=0
for i in range(1,m+1):
    maxa=0
    temp=[]
    while absort:
        if absort[0][0]<=i:
            maxa=max(maxa,absort[0][1])
            temp.append(absort.pop(0))
        else:
            break
    ans+=maxa
    temp=sorted(temp,key=lambda x:(-x[1]))
    if len(temp)>0:
        del temp[0]
    temp+=absort
    absort=sorted(temp,key=lambda x:(x[0],-x[1]))


print(ans)

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
ab=[[] for _ in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    if a < m+1:
        ab[a-1].append(-b)

h=[]
ans=0
for i in range(m):
    for j in ab[i]:
        heapq.heappush(h,j)
    if len(h)==0:
        continue
    ans+=heapq.heappop(h)*(-1)
print(ans)
### BUGGY CODE ###

def main():
    n, k, q = [int(x) for x in input().split()]

    pts = [k] * n
    ans = []
    for i in range(q):
        answerer = int(input()) - 1
        pts = [x-1 for x in pts]
        pts[answerer] += 1

    for pt in pts:
        print("Yes" if pt > 0 else "No")

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k, q = [int(x) for x in input().split()]

    cleared = [0]*n
    for _ in range(q):
        cleared[int(input()) - 1] += 1

    sum_up = sum(cleared)
    point = [k]*n
    for i in range(n):
        print("Yes" if k + (cleared[i] - sum_up) > 0 else "No")


if __name__ == "__main__":
    main()
### BUGGY CODE ###

def s(n):
	sum = 0
	for c in str(n):
		sum += int(c)
	return sum

def isSunuke(n):
	for m in range(n+1, n * 100):
		if m >= 10:
			sm = str(m)
			length = len(sm)
			nines = 0
			for c in sm:
				if c == "9":
					nines += 1
			if nines < length / 2:
				continue

		if (n / s(n)) > (m / s(m)):
			return False
	return True

k = int(input())
found=0
n = 1
while(found < k):

	if n >= 10:
		sn = str(n)
		length = len(sn)
		nines = 0
		for c in sn:
			if c == "9":
				nines += 1
		if nines < length / 2:
			n += 1
			continue

	if isSunuke(n):
		print(n)
		found+=1
	n += 1

### FIXED CODE ###

import math
# import datetime

def s(n):
	sum = 0
	for c in str(n):
		sum += int(c)
	return sum

k = int(input())
found=0

def next_sunuke(n, s_n, s_n_div):

	global found

	if n == 1:
		return

	log_n = int(math.log(n,10))
	m = n - 10 ** int(log_n // 1.25)
	# m = n - 1

	while m >= 1:
		s_m = s(m)
		s_mplus1 = s(m + 1)

		# if (s_m < s_mplus1 or (s_n - s_m != 1 and s_n - s_m != -8)) and m > 9:
		if (s_m < s_mplus1) and m > 9:
			m -= 10 ** int(log_n // 1.25)
			continue

		# print("check: " + str(m))

		s_m_div = m / s(m)

		if s_m_div <= s_n_div:
			next_sunuke(m, s_m, s_m_div)
			if found >= k:
				return

			found += 1
			# print("{0:d}".format(m), "{0:+d}".format(n-m), "{0:d}".format(s_m), s_m_div)
			print(m)
			break
		# else:
		# 	log_m = int(math.log(m,10))
		# 	if (m + 1) / (10 ** (log_m - 1)) == 19:

		# 		print ("skip: " + str(m) + " to " + str(10 ** log_m - 1))

		# 		m = 10 ** log_m - 1
		# 		s_mplus1 = s(m+1)
		# 		continue

		m -= 10 ** int(log_n // 1.25)


# 適当な大きいスヌケ数
current_sunuke = 999999999999999
s_current_sunuke = s(current_sunuke)
s_current_sunuke_div = current_sunuke / s_current_sunuke

# start = datetime.datetime.now()
next_sunuke(current_sunuke, s_current_sunuke, s_current_sunuke_div)
if found < k:
	print(current_sunuke)
# end = datetime.datetime.now()
# print(str(end-start))

# sunukes=[]

# n = current_sunuke - 1

# while(n >= 1):
# 	s_n = n / s(n)
# 	if s_n <= current_sunuke_n:
# 		#sunukes.insert(0,n)
# 		sunukes.append(n)
# 		current_sunuke = n
# 		current_sunuke_n = s_n
# 	n -= 1

# for n in sunukes:
# 	print (n)
### BUGGY CODE ###

N = int(input())
sum = 0
while(N > 0):
    sum += N%10
    N //= 10
if(sum%9==0):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N = int(input())
result = sum(list(map(int, str(N))))
if(result%9==0):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import deque
N = int(input())
a = deque()
a_num = 0
b =deque()
c = []
for i in range(N):
  a_num = int(input())
  a.append(a_num)
  k,p=0,0
  x = [0]*N
  b_num=deque()
  for i in range(a_num):
    k,p = map(int,input().split())
    b_num.append(k-1)
    x[k-1]=p
  b.append(b_num)
  c.append(x)
max_num = 0   
for i in range(2**N):
  two = format(i,"015b")
  two = two[::-1]
  flag=True
  for i,k in enumerate(two):
    if i<N:
      if k =="1":
        for l in range(a[i]):
          for j in b[i]:
            #print(b[i],c[i][j],two[j])
            if c[i][j]!=int(two[j]):
              flag =False
              break
  if flag == True:
    #print(two)
    max_num = max(max_num,two.count("1"))  
print(max_num)

### FIXED CODE ###

from collections import deque
N = int(input())
a = deque()
a_num = 0
b =deque()
c = deque()
for i in range(N):
  a_num = int(input())
  a.append(a_num)
  k,p=0,0
  x = [0]*N
  b_num=deque()
  for i in range(a_num):
    k,p = map(int,input().split())
    b_num.append(k-1)
    x[k-1]=p
  b.append(b_num)
  c.append(x)
max_num = 0   
for i in range(2**N):
  two = format(i,"015b")
  two = two[::-1]
  flag=True
  for i,k in enumerate(two):
    if flag == False:
      break
    if i<N:
      if k =="1":
        for l in range(a[i]):
          for j in b[i]:
            #print(b[i],c[i][j],two[j])
            if c[i][j]!=int(two[j]):
              flag =False
              break
          if flag ==False:
            break
        if flag == False:
          break
    
    else:
      break
  if flag == True:
    #print(two)
    max_num = max(max_num,two.count("1"))  
print(max_num)