Harryxun/stf_run huggingface dataset:
import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    geta = 64
    inf = 1<<geta
    dist = [inf] * N
    dist[s] = 0
    Q = [s]
    dp = [0]*N
    dp[s] = 1
    while Q:
        k = hpp(Q)
        dn = k>>geta
        vn = k^(dn<<geta)
        if dn > dist[vn]:
            continue
        for k in Edge[vn]:
            df = k>>geta
            vf = k^(df<<geta)
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, ((dn + df)<<geta)+vf)
            elif dist[vn] + df == dist[vf]:
                dp[vf] = (dp[vf] + dp[vn]) % MOD
    return dist, dp

MOD = 10**9+7
N, M = map(int, readline().split())
S, T = map(int, readline().split())
S -= 1
T -= 1

geta = 32
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append(d<<geta|v)
    Edge[v].append(d<<geta|u)
    

dists, dps = dijkstra(N, S, Edge)
distt, dpt = dijkstra(N, T, Edge)
st = dists[T]

onpath = [i for i in range(N) if dists[i] + distt[i] == st]

ans = dps[T]**2%MOD
for i in onpath:
    if 2*dists[i] == 2*distt[i] == st:
        ans = (ans - pow(dps[i]*dpt[i], 2, MOD))%MOD
    
    for k in Edge[i]:
        cost = k>>geta
        vf = k^(cost<<geta)
        if dists[i] + cost + distt[vf] == st:
            if 2*dists[i] < st < 2*dists[vf]:
                ans = (ans - pow(dps[i]*dpt[vf], 2, MOD))%MOD
print(ans)


### FIXED CODE ###

import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    inf = geta
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    dp = [0]*N
    dp[s] = 1
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, (dn + df,vf))
            elif dist[vn] + df == dist[vf]:
                dp[vf] = (dp[vf] + dp[vn]) % MOD
    return dist, dp

MOD = 10**9+7
N, M = map(int, readline().split())
S, T = map(int, readline().split())
S -= 1
T -= 1

geta = 10**15
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append((d, v))
    Edge[v].append((d, u))
    

dists, dps = dijkstra(N, S, Edge)
distt, dpt = dijkstra(N, T, Edge)
st = dists[T]

onpath = [i for i in range(N) if dists[i] + distt[i] == st]

ans = dps[T]**2%MOD
for i in onpath:
    if 2*dists[i] == 2*distt[i] == st:
        ans = (ans - pow(dps[i]*dpt[i], 2, MOD))%MOD
    
    for cost, vf in Edge[i]:
        if dists[i] + cost + distt[vf] == st:
            if 2*dists[i] < st < 2*dists[vf]:
                ans = (ans - pow(dps[i]*dpt[vf], 2, MOD))%MOD
print(ans)
import sys

def main():
    A, V = map(int, input().split())
    B, W = map(int, input().split())
    T = int(input())

    out = 'NO'
    t = (B - A) / (V - W)
    if t >= 0:
        if t<=T:
            out = 'YES'
    
    print(out)
main()

### FIXED CODE ###

import sys

def main():
    A, V = map(int, input().split())
    B, W = map(int, input().split())
    T = int(input())

    out = 'NO'

    if V==W:
        if B==A:
            out = 'YES'
            print(out)
            sys.exit()
        else:
            print(out)
            sys.exit()

    if B < A:
        t = (B - A) / (W - V)
    else:
        t = (B - A) / (V - W)
        
    if t >= 0:
        if t<=T:
            out = 'YES'
    
    print(out)
main()
x=input()
if (x< 1200):
  print("ABC")
elif (x<2800):
  print("ARC")
else:
  print("AGC")

### FIXED CODE ###

x = int(input())
print("ABC" if x < 1200 else ("ARC" if x < 2800 else "AGC"))
a,b=raw_input().split()
s=[1,2,3]
s.remove(x)
s.remove(y)
print s[0]

### FIXED CODE ###

a=input()
b=input()
if a==1 and b==2:
  print "3"
elif a==2 and b==3:
  print "1"
elif a==3 and b==1:
  print "2" 
elif a==3 and b==2:
  print "1"
elif a==2 and b==1:
  print "3"
else:
  print "2"
def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        if x[l[i][0]]==0:
            x[l[i][0]] = c.pop(0)
        else:
            return
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        if x[l[i][0]]==0:
            x[l[i][0]] = c.pop(0)
        else:
            return
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000) 

def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        x[l[i][0]] = c.pop(0)
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)
a, b = map(int, raw_input().split())
if a <= b:
	print a
else:
	print a - 1



### FIXED CODE ###

S = raw_input()
res = 700
for i in range(3):
	if S[i] == 'o':
		res += 100
print res
from skimage import measure

### FIXED CODE ###

n = int(input())
h = int(input())
w = int(input())
print((n-h+1)*(n-w+1))
# 文字列反転
def rev (s):
    _re=''.join(list(reversed(s)))
    return _re
 
name = ['dream','dreamer','eraser','erase']
S = input()
S_re = rev(S)
can2 = False
i= 0
while i < len(S_re):
    can = False
    can2 = False
    for div in name:
        if len(S_re[i:]) >= len(div):
            if S_re[i:i+len(div)]==rev(div) :
                i+=len(div)
                can = True
                break
    if can :
        can2 = True
    else:
        can2 = False
        break
if can2:
    print('YES')
else :
    print('No')
 
 coding: utf-8
# 文字列反転
def rev (s):
    _re=''.join(list(reversed(s)))
    return _re

name = ['dream','dreamer','eraser','erase']
S = input()
S_re = rev(S)
can2 = False
i= 0
while i < len(S_re):
    can = False
    can2 = False
    for div in name:
        if len(S_re[i:]) >= len(div):
            if S_re[i:i+len(div)]==rev(div) :
                i+=len(div)
                can = True
                break
    if can :
        can2 = True
    else:
        can2 = False
        break
if can2:
    print('YES')
else :
    print('NO')


### FIXED CODE ###

import re
print("YES" if re.match("^(dream|dreamer|erase|eraser)+$",input()) else "NO")
A = int(input())
B = int(input())
if A > 9 or B > 9:
  print(-1)
else:
  print(A*B)

### FIXED CODE ###

A,B = input().split()
A = int(A)
B = int(B)
if A > 9 or B > 9:
  print(-1)
else:
  print(A*B)
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

#C[i]=パワーがi以下の人数
C=[0]*(10**5+1)
for a in A:
    C[a]+=1
for i in range(1,len(C)):
    C[i]+=C[i-1]

#和がx以上になる組み合わせの総数を求める関数
def pattern_num_ge_x(x):
    p=0
    for a in A:
        p+=(N-(C[x-a-1] if x-a-1>=0 else 0))
    return(p)

#pattern_num_ge_x(x)がM未満になる最小のxを探す(=r)
#lはM以上になる最大のx
l=-1
r=10**5*2+1
while r-l>1:
    m=(r+l)//2
    if pattern_num_ge_x(m)<M:
        r=m
    else:
        l=m

#和がr以上になる組み合わせの総和を求める(累積和を使用)
S=[0]+list(reversed(A[:]))
for i in range(1,N+1):
    S[i]+=S[i-1]
ans=0
for a in A:
    idx=bisect.bisect_left(A,r-a)
    ans+=a*(N-idx) + S[N-idx]
    M-=(N-idx)

#回数のあまり分lを足す
ans+=l*M

print(ans)

### FIXED CODE ###

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

#和がx以上になる組み合わせの総数
def pattern_num_ge_x(x):
    p=0
    for a in A:
        ng=-1
        ok=N
        while (ok-ng)>1:
            m=(ok+ng)//2
            if a+A[m]>=x:
                ok=m
            else:
                ng=m
        p+=N-ok
    return(p)

#pattern_num_ge_x(x)がM未満になる最小のxを探す(=r)
#lはM以上になる最大のx
l=-1
r=10**10+1
while r-l>1:
    m=(r+l)//2
    if pattern_num_ge_x(m)<M:
        r=m
    else:
        l=m
#print(l,r)
#for i in range(300):
#    print(i,pattern_num_ge_x(i),sep=',')

#和がr以上になる組み合わせの総和を求める(累積和を使用)
S=list(reversed(A))
for i in range(1,N):
    S[i]+=S[i-1]
#print(S)
ans=0
for a in A:
    ng=-1
    ok=N
    while (ok-ng)>1:
        m=(ok+ng)//2
        if a+A[m]>=r:
            ok=m
        else:
            ng=m
    ans+=a*(N-ok) + (S[N-ok-1] if N-ok-1>=0 else 0)
    M-=(N-ok)
    #print(a,ok,a*(N-ok),ans)

#回数のあまり分lを足す
ans+=l*M

print(ans)
w, h, n = map(int, input().split())

x1, x2, y3, y4 = [], [], [], []

for _ in range(n):
  x, y, a = map(int, input().split())
  if a == 1:
    x1.append(x)
  elif a == 2:
    x2.append(x)
  elif a == 3:
    y3.append(y)
  else:
    y4.append(y)

print(max(min(w, min(x2)) - max(max(x1), 0), 0) * max(min(h, min(y4)) - max(max(y3), 0), 0))


### FIXED CODE ###

w, h, n = map(int, input().split())

x1, x2, y3, y4 = [0], [w], [0], [h]

for _ in range(n):
    x, y, a = map(int, input().split())
    if a == 1:
        x1.append(x)
    elif a == 2:
        x2.append(x)
    elif a == 3:
        y3.append(y)
    else:
        y4.append(y)

print(max(min(x2) - max(x1), 0) * max(min(y4) - max(y3), 0))
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
from operator import itemgetter


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


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    # 種類最小から最大までそれぞれ計算する
    N, K = LI()
    T = []
    D = []
    TD = []
    for i in range(N):
        TD.append(LI())
    #  print(T, '\n', D)
    TD = sorted(TD, key=itemgetter(1), reverse=True)
    #  print('TD', TD)

    max_value_per_type = [[t, max([td[1] for td in TD if td[0] == t])]for t in set([i[0] for i in TD])]
    #  print('max_value_per_type', max_value_per_type)
    content_per_type = [[t, [i[1] for i in TD if i[0] == t]] for t in set(i[0] for i in TD)]
    #  print(content_per_type)
    max_idx_per_type = [i[1].index([mvpt[1] for mvpt in max_value_per_type if mvpt[0] == i[0]][0]) for i in content_per_type]
    #  print('max_idx_per_type', max_idx_per_type)
    for idx, i in enumerate(max_idx_per_type):
        del content_per_type[idx][1][i]
    #  remaining_values_per_type = [[c[0], [i[0] for i in content_per_type if ]] for c in content_per_type]
    #  print('各タイプから最大値を抜きました', content_per_type)
    results = [0]
    for i in range(1, K+1):
        #  print('\n---------\n',i,'回目')
        # iを種類数とみなす
        # 何を選んだかは関係ない
        
        # 種類の全組み合わせを求める
        #  print(i)
        if len(set([i[0] for i in TD])) < i:
            break 
        combinations = list(itertools.combinations(set([i[0] for i in TD]), i))
        #  print('combi', combinations)
        type_bonus = i * i
        for combination in combinations:
            #  print('\n')
            # 各組み合わせでの最大値を求める
            current_options = [i for i in TD if i[0] in combination]
            
    print(max(results))


main()


### FIXED CODE ###

AB, BC, CA = map(int, input().split())

result = int(AB * BC / 2)

print(result)
N = int(input())
a = list(range(N))
a[0] = a[-1]
a.pop(-1)
Mmax = sum(a)

print(Mmax)

### FIXED CODE ###

N = int(input())

a = N/2
b = int(N/2)
if not(N%2 == 0):
    Mmax = N*b
elif N%2 == 0:
    Mmax = N*(b-1) + b



print(Mmax)
K=int(input())
A_b=list(map(int,input().split()))
A=A_B[0]
B=A_b[1]
m=1
for i in range(B):
  m=i*k
  if (m>A and m<B):
    print("OK")
  else:
    print("NG")
    
   
  

### FIXED CODE ###

K=int(input())
A_B=list(map(int,input().split()))
A=A_B[0]
B=A_B[1]
m=1
c=0
for i in range(A,(B+1)):
  if(i%K==0):
    c=1
    break
if(c==1):
  print("OK")
else:
  print("NG")
RDULULDURURLRDULRLR

### FIXED CODE ###

S = input()
odd = set(["R","U","D"])
even = set(["L","U","D"])
ok = True
for s in S[::2]:
    if s not in odd:
        ok = False
if len(S) > 1:
    for s in S[1::2]:
        if s not in even:
            ok = False
print("Yes" if ok else "No")
a,b = map(int,(input().split()))
print(min(a+b,a-b.a*b))

### FIXED CODE ###

a,b = map(int,(input().split()))
print(max(a+b,a-b,a*b))
a = []

for i in range(5):
    a.append(int(input()))


def ceil10(n):
    if n % 10 == 0:
        return n
    else:
        return (n // 10) * 10 + 10


def min_1(a):
    a2 = list(filter(lambda a: a > 0, (map(lambda e: e % 10, a))))

    return min(a2)


ans = sum(map(ceil10, a)) - 10 + min_1(a)
print(ans)


### FIXED CODE ###

a = []

for i in range(5):
    a.append(int(input()))


def ceil10(n):
    if n % 10 == 0:
        return n
    else:
        return ((n // 10) + 1) * 10


def min_1(a):
    a2 = list(filter(lambda a: a > 0, list(map(lambda e: e % 10, a))))

    if len(a2) == 0:
        return 10

    return min(a2)


ans = sum(map(ceil10, a)) - 10 + min_1(a)
print(ans)
N, A = map(int,input().split())

r = N%500
if r > A:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

N = int(input())
A = int(input())

r = N % 500
if r > A:
    print("No")
else:
    print("Yes")
print('safe' if int(input()) > int(input()) else 'unsafe')

### FIXED CODE ###

s, w = map(int, input().split())
print('safe' if s > w else 'unsafe')
from scipy.special import comb

N, M = map(int, input().split())
print(comb(N, 2, exact=True) + comb(M, 2, exact=True))



### FIXED CODE ###

N, M = map(int, input().split())
print(int(N*(N-1)/2+M*(M-1)/2))
n,m,X,Y=sorted(map(int,input().split()))
x=max([X],max(map(int,input().split())))
y=min([Y],min(map(int,input().split())))
print("No War" if x<y else "War")

### FIXED CODE ###

def main():
    a=sorted(map(int,input().split()))
    print(a[2]*10+a[0]+a[1])
    
if __name__ == "__main__":
    main()
# -*- coding: utf-8 -*-

def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] =min(d[i][j],d[i][k] + d[k][j])            
    return d

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

d = [[float("inf") for i in range(N)] for i in range(N)]

for i in range(M):
    A, B, C = map(int, input().split())
    if C <= L:
        d[A-1][B-1] = C
        d[B-1][A-1] = C
for i in range(N):
    d[i][i] = 0

s = [[0] * N for _ in range(N)]
d2 = warshall_floyd(d)

for i in range(N):
    for j in range(N):
        if d2[i][j] <= L:
            s[i][j] = 1
            s[j][i] = 1

warshall_floyd(s)



Q = int(input())

for i in range(Q):
    s, t = map(int, input().split())
    if s[s][t] > 0:
        print(s[s][t] -1)
    else:
        print(-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import floyd_warshall

"""
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] =min(d[i][j],d[i][k] + d[k][j])            
    return d
"""
N, M, L = map(int, input().split())

d = [[0 for i in range(N)] for i in range(N)]

for i in range(M):
    A, B, C = map(int, input().split())
    d[A-1][B-1] = C
    d[B-1][A-1] = C

d = floyd_warshall(d, directed = False)
S = [[0 for i in range(N)] for i in range(N)]


for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            S[i][j] = 1
            S[j][i] = 1
            
S = floyd_warshall(S, directed = False)

Q = int(input())

for i in range(Q):
    s, t = map(int, input().split())
    if S[s-1][t-1] == float("inf"):
        print(-1)
    else: 
        print(int(S[s-1][t-1]-1))
import sys
inputs = sys.stdin.readlines()

from collections import deque, defaultdict

def dfs_generator(nodes, start):
    nexts = deque([start])
    while nexts:
        node = nexts.popleft()
        nexts.extend(nodes[node]['childs'])
        yield node

nodes = dict({1: dict({'val': 0, 'childs': []})})
for x in inputs[1:n]:
    from_, to_ = map(int, x.split())
    nodes[from_]['childs'].append(to_)
    nodes[to_] = dict({'val': 0, 'childs': []})

subtree_roots = defaultdict(int)
for x in inputs[n:]:
    n, v = map(int, x.split())
    subtree_roots[n] += v
'''
subtrees = defaultdict(list)
for r, v in subtree_roots.items():
    gen = dfs_generator(nodes, r)
    try:
        while True:
            node = next(gen)
            subtrees[r].append(node) 
    except StopIteration:
        pass
    for n in subtrees[r]:
        nodes[n]['val'] += v

for i in range(1, n):
    print(str(nodes[i]['val']), end=' ')
print(str(nodes[i+1]['val']))
'''

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q = map(int,readline().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:N+N-2])
PX = iter(ABPX[N+N-2:])

graph = [[] for _ in range(N+1)]
for a,b in zip(AB,AB):
    graph[a].append(b)
    graph[b].append(a)

val = [0] * (N+1)
for p,x in zip(PX,PX):
    val[p] += x

stack = [1]

parent = [0] * (N+1)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        val[y] += val[x]

print(' '.join(map(str,val[1:])))
n=int(input())
if n==1:print("Hello world")
else:
    a,s=map(int,input().split())
    print(a+s)

### FIXED CODE ###

n=int(input())
if n==1:print("Hello World")
else:
    a,s=int(input()),int(input())
    print(a+s)
N = int(input())
total = 0.0
for i in range(N):
    money, tani = input().split()
    money = float(money)
    if tani = "JPY":
        total += money
    else:
        total += money * 380000.0
print("%f"%(total))

### FIXED CODE ###

year, month, day = map(int, input().split("/"))
if year <= 2019 and month <= 4 and day <= 30:
    print("Heisei")
else:
    print("TBD")
n=int(input())
s=input()
dp=[[0]*n+1 for i in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
        if s[j]==s[i] and dp[i+1][j+1]+1<=j-i:
            dp[i][j]=dp[i+1][j+1]+1
ans=0
for i in range(n):
    for j in range(n):
        ans=max(ans,dp[i][j])
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
dp=[[0]*n for i in range(n)]
for i in range(n-2,-1,-1):
    for j in range(n-1,i,-1):
        if j==n-1:
            if s[j]==s[i]:
                dp[i][j]=1
        else:
            if s[j]==s[i] and dp[i+1][j+1]+1<=j-i:
                dp[i][j]=dp[i+1][j+1]+1
            else:
                dp[i][j]=0
ans=0
for i in range(n):
    for j in range(n):
        ans=max(ans,dp[i][j])
print(ans)
x,y,a,b,c=map(int,input().split())
p=sorted(list(map(int,input().split())))[-x-y:]
q=sorted(list(map(int,input().split())))[-x-y:]
r=sorted(list(map(int,input().split())))
for i in range(len(p)):
  r.append(p[i])
  r.append(q[i])
r=sorted(r)[-x-y:]
print(sum(r))



### FIXED CODE ###

x,y,a,b,c=map(int,input().split())
p=sorted(list(map(int,input().split())))[-x:]
q=sorted(list(map(int,input().split())))[-y:]
r=sorted(list(map(int,input().split())))
for i in range(len(p)):
  r.append(p[i])
for i in range(len(q)):
  r.append(q[i])
r=sorted(r)[-x-y:]
print(sum(r))
n=int(input())
A=[]
X=[]
Y=[]
x=[]
y=[]
l=[1]*n
for i in range(n):
  a=int(input())
  A.append(a)
  for j in range(a):
    x1,y1=[int(s) for s in input().split()]
    x.append(x1)
    y.append(y1)
  X.append(x)
  Y.append(y)
  
c=0
for i in range(n):
  for j in range(i, n):
    if l[j]==0:continue
    for k in range(A[j]):
    　　l[X[j][k]] *= Y[j][k]
  if c<l.count(1):
    c=l.count(1) 
  
        
  
print(c)  
  
  
  
  
  
  
  
  
  
  
  
  
  

### FIXED CODE ###

n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)
import math
from decimal import *
a,b,c = map(int,input().split())
if a+b >= c:
    print('No')
else:
    sq = Decimal(((a*b)**(1/2))*2)
    if (a+b+sqin) <c:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

a,b,c = map(int,input().split())

if c-a-b>0:
    if 4*a*b<(c-a-b)**2:
        print('Yes')
    else:
        print('No')
else:
    print('No')
N = int(input())
s = ["" for i in range(N)]
t = [0 for i in range(N)]
for i in range(N):
    s_str, t_str = input().split()
    s[i] = s_str
    t[i] = int(t_str)
    
X = input()
ans = 0
count = False
for i in range(X):
    if count:
        ans += t[i]
    if s[i] == X:
        count = True
print(ans)

### FIXED CODE ###

N = int(input())
s = ["" for i in range(N)]
t = [0 for i in range(N)]
for i in range(N):
    s_str, t_str = input().split()
    s[i] = s_str
    t[i] = int(t_str)
    
X = input()
ans = 0
count = False
for i in range(N):
    if count:
        ans += t[i]
    if s[i] == X:
        count = True
print(ans)
# -*- coding: utf-8 -*-
# 整数の入力
inputs = []
inputs.append(int(input()))
inputs.append(int(input()))
inputs.append(int(input()))
inputs.append(int(input()))
inputs.append(int(input()))
amari_list = []
time = 0
for input in inputs:
  amari = input % 10
  if amari == 0:
    time += input
  else:
    time += (input // 10) * 10
    amari_list.append(amari)
time += (len(amari_list) - 1)*10
time += min(amari_list)
# 出力
print(time)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
inputs = []
inputs.append(int(input()))
inputs.append(int(input()))
inputs.append(int(input()))
inputs.append(int(input()))
inputs.append(int(input()))
amari_list = []
time = 0
for input in inputs:
  amari = input % 10
  if amari == 0:
    time += input
  else:
    time += (input // 10) * 10
    amari_list.append(amari)
if len(amari_list) > 0:
  time += (len(amari_list) - 1)*10
  time += min(amari_list)
# 出力
print(time)
S = raw_input()
if S = 'ABC':
	print 'ARC'
else:
	print 'ABC'

### FIXED CODE ###

S = raw_input()
if S == 'ABC':
	print 'ARC'
else:
	print 'ABC'
-*- coding: utf-8 -*-

N = int(input())
A = list(map(int, input().split()))
sheet = [0]*(N)
for i in range(N-1):
    sheet[A[i]-1]=sheet[A[i]-1]+1


for i in range(N):
    print("{}".format(sheet[i]))


### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())
A = list(map(int, input().split()))
sheet = [0]*(N)
for i in range(N-1):
    sheet[A[i]-1]=sheet[A[i]-1]+1


for i in range(N):
    print("{}".format(sheet[i]))
import numpy as np
n,x=map(int,input().split())
xl=list(map(int,input().split()))

xl.append(x)

arr=np.array(xl)

p=min(arr)
arrr=arr-p
print(np.gcd.reduce(arrr))


### FIXED CODE ###

import numpy as np
from fractions import gcd
n,x=map(int,input().split())
xl=list(map(int,input().split()))

xl.append(x)


p=min(xl)
ans=x-p
for i in range(n+1):
    ans=gcd(xl[i]-p,ans)
print(ans)