Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3

import sys
import math
import itertools

def required_visit_time(t, shop):
    a, b = shop
    return int((t - b) / (a + 1)) - 1

# shops はソート済み
def calc_dp_time(T, shops):
    t = T
    for s in shops:
        t = required_visit_time(t, s)
    return t

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = list(tuple(map(int, sys.stdin.readline().split())) for _ in range(N))

    shops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    dpmemo = {}

    def dp(i, t):
        assert i >= 0
        assert t >= 0

        if i == 0:
            return 0

        if (i, t) in dpmemo:
            return dpmemo[i, t]

        h = i - 1
        r = required_visit_time(t, shops[h])
        n = max(dp(h, r) + 1, dp(h, t)) if r >= 0 else dp(h, t)
        dpmemo[i, t] = n
        return n

    #
    # 解に含まれ得る a=0 要素を二分探索
    #
    dpmax = sum(1 for _ in itertools.takewhile(lambda x: x[0] > 0, shops))
    l = dpmax
    r = N + 1
    while l + 1 < r:
        m = int((l + r) / 2)
        if calc_dp_time(T, shops[dpmax:m]) < 0:
            r = m
        else:
            l = m

    ans = 0
    for i in range(l, dpmax - 1, -1):
        t = calc_dp_time(T, shops[dpmax:i])
        n = dp(dpmax, t) + (i - dpmax)
        if n <= ans:
            break
        ans = n

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env pypy3

import sys
import math
import itertools
import bisect

INF = int(1e18)
T_MAX = int(1e9)

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

    nzshops = [(a, b) for a, b in shops if a > 0]
    zshops  = [(a, b) for a, b in shops if a == 0]

    nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    zshops.sort()

    dp = [[0] + [INF] * int(math.log(T_MAX, 2)) for _ in range(len(nzshops) + 1)]
    for i in range(1, len(dp)):
        for c in range(1, len(dp[i])):
            a, b = nzshops[i - 1]
            t = dp[i - 1][c - 1] + 1
            dp[i][c] = min(dp[i - 1][c], t + t * a + b)

    rs = list(itertools.accumulate(1 + b for _, b in zshops))
    ans = max(c + bisect.bisect(rs, T - dp[-1][c])
            for c in range(len(dp[-1])) if dp[-1][c] <= T)

    print(ans)

if __name__ == '__main__':
    main()
n = int(input())
d = list(map(int,input().split()))
mod = 998244353

if d[0] != 0:
    print(0)
    exit()

a = [0]*(n-1)

while d:
    s = d.pop()
    a[s] += 1

if a[0] >= 2:
    print(0)
    exit()

ans = 1

for i in range(n-2):
        ans *= a[i]**a[i+1]
        ans %= mod

print(ans % mod)

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
mod = 998244353

if d[0] != 0:
    print(0)
    exit()

if n == 1:
        print(1)
        exit()

if n == 2:
    if d[1] == 1:
        print(1)
        exit()
    else:
        print(0)
        exit()


a = [0]*n

while d:
    s = d.pop()
    a[s] += 1

if a[0] >= 2:
    print(0)
    exit()

ans = 1

for i in range(n-1):
        ans *= a[i]**a[i+1]
        ans %= mod

print(ans % mod)
mod = 998244353

N, S, *A = map(int, open(0).read().split())

dp = [1] + [0] * S
for i, a in enumerate(A):
    for j in reversed(range(S + 1)):
        dp[j] = (2 * dp[j] + dp[j - a] * (j >= a)) % mod

print(dp[S])

### FIXED CODE ###

mod = 998244353

N, S, *A = map(int, open(0).read().split())

dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i, a in enumerate(A):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod

        if j + a <= S:
            dp[i + 1][j + a] += dp[i][j]
            dp[i + 1][j + a] %= mod

print(dp[N][S])
A, B, K = map(int, input().split())
ans=[]
for i in range(1,int(max([A,B]))):
        if A%i== 0 and B%i == 0:
            ans.append(i)
print(ans[K-1])

### FIXED CODE ###

A, B, K = map(int, input().split())
ans=[1]
for i in range(2,int(max([A,B])+1)):
        if A%i== 0 and B%i == 0:
            ans.append(i)
ans.sort(reverse=True)
print(ans[K-1])
s = inupt()
print(s.count('1'))

### FIXED CODE ###

s = input()
print(s.count('1'))
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(1000000)

def dfs(x, y, sym):
	tile[x][y] = '.'
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if nx>=0 and nx<N and ny>=0 and ny<M and tile[nx][ny]==sym:
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			if not tile[i][j] == '.':
				if tile[i][j] == '@':
					dfs(i, j, '@')
					res += 1
				elif tile[i][j] == '#':
					dfs(i, j, '#')
					res += 1
				elif tile[i][j] == '*':
					dfs(i, j, '*')
					res += 1
	print(res)

index = 0	
counter=0 
DX = [-1, 0, 1, 0]
DY = [0, -1, 0, 1]
while True:
	counter+=1
	line = input()
	if ' ' in line:
		N = int(line.split(' ')[0])
		M = int(line.split(' ')[1])
		tile = [[0 for i in range(N)]for j in range(M)]
	else:
		tile[counter-2] = list(line)
	if N==0 and M==0:
		break
	if counter-1==M:
		solve()
		counter = 0

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym):
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1,0,1,0]
DY = [0,-1,0,1]
sys.setrecursionlimit(10**7)
while True:
	line = input()
	if " " in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(M)] for j in range(N)]
	else:
		tile[counter-1] = list(line)
	if N is 0 and M is 0:
		break
	counter += 1
	if counter-1 is N:
		solve()
		counter = 0
k = input().split('')[1]
sticks = sorted(list(map(int,input().split(''))),reverse=True)

total = 0

for i in range(k):
    total += sticks[i]

print(total)

### FIXED CODE ###

k = int(input().split()[1])
sticks = sorted(list(map(int,input().split())),reverse=True)

total = 0

for i in range(k):
    total += sticks[i]

print(total)
n = int(input())

s = []
for i in range(n):
    s.append(list(input()))

result = 0
for offset in range(n):
    is_symmetry = True
    for i in range(n):
        for j in range(i+1, n):
            if s[i][(j+offset)%n] != s[j][(i+offset)%n]:
                is_symmetry = False
                break
        if not is_symmetry:
            break
    if is_symmetry:
        result += n
        # print('offset: %i' % offset)

print(result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
for i in range(n):
    s.append(s[-1] + a[i])
s.sort()
result = 0

count = 1
for i in range(n):
    if s[i] == s[i+1]:
        count += 1
    else:
        result += count * (count - 1) // 2
        count = 1
result += count * (count - 1) // 2

print(result)
x = int(input())
a = 0
b = 0

for a_ in range(3):
    _ = a_**5 - x
    b_ = _**0.2
    if a_**5 - b_**5 ==x:
        a = a_
        b = b_**5
        
print(a, int(b))

### FIXED CODE ###

x = int(input())
a = 0
b = 0

for a_ in range(-500, 500):
    for b_ in range(-500, 500):
        if a_**5 - b_**5 ==x:
            a = a_
            b = b_
            break
            
print(a, b)
a,b=map(int,input().split())
prinp(b*2-a)

### FIXED CODE ###

a=int(input())
b=int(input())
print(b*2-a)
a,b=map(int,input().split())
c=list(map(int,input().split()))
required=sum(c)/(4*b)
count=0
for d in ｃ:
    if d>=required:
        count+=1
    else:
        break
print("YNeos"[count<b::2])

### FIXED CODE ###

a,b,c=map(int,input().split())
print(c,a,b)
s = input()
acgt = ['A', 'C', 'G', 'T']
ans = 0
for si in s:
    if si in acgt:
        cnt += 1
        ans = max(ans, cnt)
    else:
        cnt = 0
    #print(ans)
print(ans)

### FIXED CODE ###

s = input()
acgt = ['A', 'C', 'G', 'T']
ans = 0
cnt = 0
for si in s:
    if si in acgt:
        cnt += 1
        ans = max(ans, cnt)
    else:
        cnt = 0
    #print(ans)
print(ans)
n = int(input())
a = list(map(int, input().split()))
result = 0
d = 0
for i in range(n):
  d += a[i] ** 2
result = int(((sum(a) % (10**9 + 7)) ** 2 - d) / 2)
result = result % (10**9 + 7)
print(result)

### FIXED CODE ###

d, t, s = map(int, input().split())
if s * t < d:
  print("No")
else:
  print("Yes")
N = int(input())
d = list(map(int,input().split()))
dunder = 0
count = 0
for i in range():
    dunder = sum (x<i for x in d)
    if 2*dunder == len(d):
        count += 1
    elif 2*dunder > len(d):
        break
print(count)


### FIXED CODE ###

N = int(input())
d = list(map(int,input().split()))
d.sort()
m = N//2
if d[m] == d[m-1]:
    print(0)
else:
    print(d[m]-d[m-1])
S, T = input().split()
ans = 0
for i in range(3):
    if S[i]==T[i]:
        ans += 1
    else:
        pass
print(ans)

### FIXED CODE ###

S, T = input(), input()
ans = 0
for i in range(3):
    if S[i]==T[i]:
        ans += 1
    else:
        pass
print(ans)
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
s = set()
for i in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    s.add(y)
    graph[x].append(y)

def dfs(x):
    if not graph[x]:
        return 1
    stack = graph[x]
    while stack:
        now = stack.pop(0)
        ret = 0
        ret = max(ret,dfs(now)+1)
    return ret

ans = 0
for i in range(N):
    if i not in s:
        ans = max(ans,dfs(i))
print(ans)
        

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline  #文字列入力では注意！
from copy import deepcopy
from functools import lru_cache
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
s = set()
for i in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    s.add(y)
    graph[x].append(y)

@lru_cache(maxsize = None)
def dfs(x):
    if not graph[x]:
        return 0
    stack = deepcopy(graph[x])
    ret = 0
    while stack:
        now = stack.pop(0)
        ret = max(ret,dfs(now)+1)
    return ret

ans = 0
for i in range(N):
    if i not in s:
        ans = max(ans,dfs(i))
print(ans)
def gcd(a,b):
  if b == 0:return 1
  return gcd(b,a%b)

N=int(input())
T=[]
for i in range(N):
  t = int(input())
  T.append(t)
  if i == 0:continue
  elif i == 1:
    lcm = T[-2]*T[-1]//gcd(T[-2],T[-1])
  else:
    lcm = lcm * T[-1]//gcd(lcm,T[-1])

print(lcm)

### FIXED CODE ###

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

N=int(input())
T=[]
if N==1:
  print(input())
  exit()
for i in range(N):
  t = int(input())
  T.append(t)
  if i == 0:continue
  elif i == 1:
    lcm = T[-2]*T[-1]//gcd(T[-2],T[-1])
  else:
    lcm = lcm * T[-1]//gcd(lcm,T[-1])

print(lcm)
HM = input().split()
H, M = [int(HM[i]) for i in range(len(HM))]

S = [input() for i in range(H)]
print(S)
#print(T[0][1])
#S2 = list([S[i] for i in range(H)] for j in range(M))
S2 = []
for i in range(H):
    S2.append(list(S[i]))
print(S2)

def minesweeper():
    for i in range(H):
        for j in range(M):
            if S[i][j] == ".":
                c = count(i, j)
                #print(c)
                S2[i][j] = c
    for i in range(H):
        for j in range(M-1):
            print(S2[i][j], end="")
        print(S2[i][M-1])
    return 0


def count(x,y):
    c = 0
    #print("x={}".format(x))
    if (x >= 1 and y >= 1):
        if S[x-1][y-1] == '#':
            c += 1
            #print('1')
    if (x >= 1):
        if S[x-1][y] == "#":
            c += 1
            #print('2')
    if x >= 1 and y <= M - 2:
        if S[x-1][y+1] == "#":
            c += 1
            #print("x={}".format(x))
            #print('3')
    if (y >= 1):
        if S[x][y-1] == "#":
            c += 1
            #print('4')
    if (y <= M - 2):
        if S[x][y+1] == "#":
            c += 1
            #print('5')
    if (x <= H-2 and y >= 1):
        if S[x+1][y-1] == "#":
            c += 1
            #print('6')
    if (x <= H-2):
        if S[x+1][y] == "#":
            c += 1
            #print('7')
    if (x <= H-2 and y <= M-2):
        if S[x+1][y+1] == "#":
            c += 1
            #print('8')
    return c

minesweeper()

### FIXED CODE ###

rng1 = -100
rng2 = 101
#print(input().split())
inp = [int(i) for i in input().split()]
#print(inp)
x, y, z = [inp[i] for i in range(len(inp))]
#print("x={},y={},z={}".format(x,y,z))

def dif1(x, y ,z):
    if not isinstance(x, int) or not isinstance(y, int) or not isinstance(z, int):
        return False
    elif x not in range(rng1, rng2) or y not in range(rng1, rng2)or z not in range(rng1, rng2):
        return False
    else:
        if y == z:
            return x
        if z == x:
            return y
        if x == y:
            return z
Ans = dif1(x,y,z)
print(Ans)
import math

r = import()

print ("%f.6 %f.6" % (math.pi*r*r, math.2*pi*r))

### FIXED CODE ###

import math

r = input()

print("%f %f" % (math.pi * r ** 2, 2 * math.pi * r))
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=[];C=[];Q=[]
A.sort()
for i in range(m):
    b,c=map(int,input().split())
    Q.append([b,c])

import bisect as bi

#Qの統合
s=set([l[1] for l in Q])
dicts={}
for i in s:
    dicts[s]=0
for l in Q:
    dicts[l[1]]+=l[0]
Q=[[j,i] for i,j in dicts.items()]
Q=sorted(Q, key=lambda x:x[1], reverse=1)
######
print(Q)

for l in Q:
    b,c=l
    a=bi.bisect_left(A,c)
    if A[0]>=c:
        break
    if a< b:
        A=[c]*a + A[a:]
        break
    
    A= A[b:a]+ [c]*b + A[a:]
    print(A)
print(sum(A))

### FIXED CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
Q=[]
for i in range(m):
    b,c=map(int,input().split())
    Q.append([b,c])

Q=sorted(Q, key=lambda x:x[1], reverse=1)
kae=0

d=[-1]*(n)
now=0
for l in Q:
    b,c=l
    if n-now<b:
        d[now:]=[c]*(n-now)
        break
    d[now:now+b]=[c]*b
    now+=b

#print(d)
ans=sum(A)
now=ans
for kae in range(1,n+1):
    now+=d[kae-1]
    now-=A[kae-1]
    ans=max(ans,now)
print(ans)
n = int(input())
l_before = input()

l = l_before.split(' ')
lnum = len(l)


i = 0
j = 0
k = 0

count = 0

for ic in range(lnum):
    for jc in range(lnum-ic-1):
        for kc in range(lnum-ic-jc-1):
            i = ic
            j = ij + ic
            k = ij + ic +ik
            if i + j >= k:
                count = count + 1
            else:
                if i + k >= j:
                    count = count + 1
                else:
                    if k + j >= i:
                        count = count + 1

print(count)


### FIXED CODE ###

n = int(input())
l_before = input()

l = l_before.split(' ')



i = 0
j = 0
k = 0

count = 0

for ic in range(n):
    for jc in range(n-ic-1):
        for kc in range(n-ic-jc-2):
            i = ic
            j = i + jc + 1
            k = j + kc + 1
            if int(l[i]) != int(l[j]):
                if int(l[j]) != int(l[k]):
                    if int(l[i]) != int(l[k]):
                        if int(l[i]) >= int(l[j]):
                            if int(l[k]) >= int(l[i]):
                                if int(l[k]) < int(l[i]) + int(l[j]):
                                    count = count + 1
                            else:
                                if int(l[i]) < int(l[k]) + int(l[j]):
                                    count = count + 1
                        else:
                            if int(l[k]) > int(l[j]):
                                if int(l[k]) < int(l[i]) + int(l[j]):
                                    count = count + 1
                            else:
                                if int(l[j]) < int(l[k]) + int(l[i]):
                                    count = count + 1

print(count)
import numpy as np

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

A = []
for i in range(n):
    A.append(list(map(int, input().split())))

b = []
for i in range(m):
    b.append(int(input()))

c = np.array(A).dot(b)

for ci in c:
    print(ci)

### FIXED CODE ###

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

A = []
for i in range(n):
    A.append(list(map(int, input().split())))

b = [0] * m
for i in range(m):
    b[i] = int(input())

from operator import mul
for i in range(n):
    print(sum(map(mul, A[i], b)))
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]

A.sort()
BC.sort(key=lambda x:x[1], reverse=True)
pos = 0
for b, c in BC:
    for i in range(pos, pos + b):
        if A[i] < c:
            A[i] = c
        else:
            break
    pos = i + 1
    if pos >= n:
        break

print(sum(A))


### FIXED CODE ###

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

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

pos = 0
for b, c in BC:
    end = (pos + b) if pos + b <= n else n
    for i in range(pos, end):
        if A[i] < c:
            A[i] = c
        else:
            break
    pos = i + 1
    if pos >= n:
        break

print(sum(A))
X = int(input())
dp = [0]*(X+1)
dp[0] = 1
dp[100] = 1
dp[101] = 1
dp[102] = 1
dp[103] = 1
dp[104] = 1
dp[105] = 1
for i in range(100, X+1):
    for j in range(6):
        dp[i] = max(dp[i], dp[i-100+j])

if dp[X]:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import sys
X = int(input())
if 1 <= X and X < 100:
    print("0")
    sys.exit()
i = 0
dp = [0]*(X+1)
dp[0] = 1
for i in range(100, X+1):
    for j in range(6):
        if dp[i-(100+j)] == 0:
            pass
        else:
            dp[i] = 1
print(dp[X])
while True:
 h,w=map(int,input().split())
 if h==0:break
 for y in range(h):
  ''join([*]**w)

### FIXED CODE ###

while 1:
 h,w=map(int,input().split())
 if h==0:break
 print(('#'*w+'\n')*h)
print x*x*x

### FIXED CODE ###

x = int(input())
cube = x*x*x
print cube
s_input_sort = sorted(list(str(input())))
t_input_sort = sorted(list(str(input())), reverse=True)

s_str = "".join(s_input_sort)
t_str = "".join(t_input_sort)

if t_str >= s_str:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

s_input_sort = sorted(list(str(input())))
t_input_sort = sorted(list(str(input())), reverse=True)

s_str = "".join(s_input_sort)
t_str = "".join(t_input_sort)

if s_str == t_str:
    print("No")
else:    
    if t_str < s_str:
        print("No")
    else:
        print("Yes")
#! /usr/bin/env python
# -*- coding: utf-8 -*-

def rec(y, x, used, TILE):
    if (not(0<=x<W)) or (not(0<=y<H)) or (TILE[y][x]==0) or (used[y][x]==1):
        return 0
    else:
        used[y][x] = 1
        rec(y-1, x-1, used, TILE)
        rec(y-1, x, used, TILE)
        rec(y-1, x+1, used, TILE)
        rec(y, x-1, used, TILE)
        rec(y, x, used, TILE)
        rec(y, x+1, used, TILE)
        rec(y+1, x-1, used, TILE)
        rec(y+1, x, used, TILE)
        rec(y+1, x+1, used, TILE)
    return 1

(W, H) = map(int, raw_input().split())
while W!=0 :
    used = [[0]*W for i in range(H)]
    TILE = []
    for i in range(H):
        TILE.append(map(int, raw_input().split()))

    Sum = 0
    for i in range(H):
        for j in range(W):
            if used[i][j] == 0 and TILE[i][j] == 1:
                Sum += rec(i, j, used, TILE)
    print Sum
    #print used.count(1)

    (W, H) = map(int, raw_input().split())

### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

def rec(y, x, used, TILE):
    if (not(0<=x<W)) or (not(0<=y<H)) or (TILE[y][x]==0) or (used[y][x]==1):
        return 0
    else:
        used[y][x] = 1
        rec(y-1, x-1, used, TILE)
        rec(y-1, x, used, TILE)
        rec(y-1, x+1, used, TILE)
        rec(y, x-1, used, TILE)
        rec(y, x, used, TILE)
        rec(y, x+1, used, TILE)
        rec(y+1, x-1, used, TILE)
        rec(y+1, x, used, TILE)
        rec(y+1, x+1, used, TILE)
    return 1

(W, H) = map(int, raw_input().split())
while W!=0 :
    used = [[0]*W for i in range(H)]
    TILE = []
    stack = []
    for i in range(H):
        TILE.append(map(int, raw_input().split()))
    Sum = 0
    for i in range(H):
        for j in range(W):
            if used[i][j] == 0 and TILE[i][j] == 1:
                Sum += 1
                stack.append([i, j])
                while len(stack)>0:
                    cur = stack[len(stack)-1]
                    stack.pop()
                    for y in [-1, 0, 1]:
                        for x in [-1, 0, 1]:
                            if 0<=cur[0]+y<H and 0<=cur[1]+x<W and TILE[cur[0]+y][cur[1]+x]==1 \
                                    and used[cur[0]+y][cur[1]+x]==0:
                                stack.append([cur[0]+y, cur[1]+x])
                                used[cur[0]+y][cur[1]+x] = 1

    """for i in range(H):
        for j in range(W):
            if used[i][j] == 0 and TILE[i][j] == 1:
                Sum += rec(i, j, used, TILE)
    print Sum"""
    print Sum
    #print used.count(1)

    (W, H) = map(int, raw_input().split())
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]


    seen = [None]*n
    def dfs(graph,s):
        seen[s] = s+1
        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    for i in range(k):
        c,d = map(int, input().split())
        bgraph[d-1].append(c)
        bgraph[c-1].append(d)

    # print(fgraph)
    #print(bgraph)
    rk = [list()]*n
    for i in range(n):
        seen = [None]*n
        dfs(fgraph, i)
        rk[i] = seen
    
    # print(rk)
    # print(fgraph)
    for i in range(n):
        non = {None}
        me = {i+1}
        srk = set(rk[i])-non
        bg = set(bgraph[i])
        fg = set(fgraph[i])

        print(len(srk-bg-fg-me))
        
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    is_all_seen = [False]*n
    cnt = 0
    seen = [None]*n
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    def dfs(graph,s,r):
        seen[s] = s+1
        if rks[s] is None:
            rks[s] = r

        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):

        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()
import string

count = {x: 0 for x in string.ascii_lowercase}
lines = ""

while True:
    try:
        lines += input().lower()
    except EOFError:
        break

s = input().lower()

for c in s:
    if 'a' <= c <= 'z':
            count[c] += 1

for key, num in count:
    print("{0} : {1}".format(key, count[key]))

### FIXED CODE ###

import string

count = {x: 0 for x in string.ascii_lowercase}
lines = ""

while True:
    try:
        lines += input().lower()
    except EOFError:
        break

for c in lines:
    if 'a' <= c <= 'z':
            count[c] += 1

for key in string.ascii_lowercase:
    print("{0} : {1}".format(key, count[key]))