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

import numpy as np


def main():
    H, W = map(int, input().split())
    A = np.zeros([H, W])
    for h in range(H):
        A[h, :] = list(map(lambda x: 1 if x == "#" else 0, input()))

    costs = np.zeros([H, W])
    dd = ((1, 0), (-1, 0), (0, 1), (0, -1))

    s = np.where(A == 1)
    s = np.array(s)
    len_s = s.shape[1]
    q = []
    for i in range(len_s):
        q.append((s[0, i], s[1, i]))

    moves = 0

    while q:
        qn = []
        moves += 1
        for x, y in q:
            for dx, dy in dd:
                nx, ny = int(x + dx), int(y + dy)
                if 0 <= nx < H and 0 <= ny < W:
                    if A[nx, ny] == 0:
                        costs[nx, ny] = moves
                        A[nx, ny] = 1
                        qn.append((nx, ny))

        q = qn
        if np.all(A == 1):
            break

    print(int(np.max(costs)))


main()


### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    field = [list(input()) for _ in range(H)]
    dd = ((1, 0), (-1, 0), (0, 1), (0, -1))

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

    while q:
        qn = []
        moves += 1
        for x, y in q:
            for dx, dy in dd:
                nx, ny = int(x + dx), int(y + dy)
                if 0 <= nx < H and 0 <= ny < W:
                    if field[nx][ny] == ".":
                        field[nx][ny] = moves
                        qn.append((nx, ny))

        q = qn

    m = []
    for i in range(H):
        m.append(max(field[i]))
    print(max(m))


main()
### BUGGY CODE ###

A,B,K = map(int, input().split())
if A - B > 2 * K:
  [print(i) for i in range(A,A+K) if i - K < A]
  [print(i) for i in range(B+1-K,B+1) if i + K > B]
else:
  [print(i) for i in range(A,B+1) if i - K < A or i + K > B]

### FIXED CODE ###

A,B,K = map(int, input().split())
if B-A > 2 * K:
  [print(i) for i in range(A,A+K)]
  [print(i) for i in range(B+1-K,B+1)]
else:
  [print(i) for i in range(A,B+1) if i - K < A or i + K > B]
### BUGGY CODE ###

h, w = [int(i) for i in input().split()]
a = []
b = [""] * w
for _ in range(h):
    s = input()
    a.append(s)
    for i, j in enumerate(s):
        b[i] += j


def c(s):
    m = 0
    n = 0
    for i in s:
        if i == ".":
            n += 1
        else:
            m = max(n, m)
            n=0
    m = max(n, m)
    return m


print(c(max(a, key=c)) + c(max(b, key=c)) - 1)


### FIXED CODE ###

h, w = [int(i) for i in input().split()]
s = [input() for _ in range(h)]

a = [[0]*w for _ in range(h)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for i in range(h):
    k = 0
    for j in reversed(range(w)):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for j in range(w):
    k = 0
    for i in range(h):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for j in range(w):
    k = 0
    for i in reversed(range(h)):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
b = max([max(i) for i in a])
print(0 if b == 0 else b-3)
### BUGGY CODE ###

args = int(input().rstrip())

def snuke(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

def find_snuke(args):
    result = []
    i = 1
    while len(result) < args:
        push = True
        p = 0
        for power in range(0,len(str(i))):
            if((i+10**power)/snuke(i+10**power))<(i/snuke(i)):
                push = False
                p = power
        if push:
            result.append(i)
        i=i+10**p
            
    return result

arr = find_snuke(args)
for a in arr:
   print(a)

### FIXED CODE ###

args = int(input().rstrip())

def snuke(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

def find_snuke(args):
    result = []
    i = 1
    while len(result) < args:
        push = True
        p = 0
        for power in range(0,len(str(i))):
            if((i+10**power)/snuke(i+10**power))<(i/snuke(i)):
                push = False
                p = power
                break
        if push:
            result.append(i)
        i=i+10**p
            
    return result

arr = find_snuke(args)
for a in arr:
   print(a)
### BUGGY CODE ###

def decision(s,td,index):
    #index番目の文字が落ちるかどうかを判別
    #右に落ちるときは1，左に落ちるときは-1，落ちないときは0を返す
    global N,Q
    qi = 0
    j = index
    while qi < Q and (j >= 0 and j < N):
        if s[j] == td[qi][0]:
            if td[qi][1] == 'L':
                j -= 1
            elif td[qi][1] == 'R':
                j += 1
        qi += 1
    if j == -1:
        return -1
    elif j == N:
        return 1
    else:
        return 0
    


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

td = [0] * Q
for i in range(Q):
    td[i] = (input().split())
    
#td[i][j]:i番目の文字(j=0)と方向(j=1)
    
    
#2分探索
left = 0
right = N-1
#右側のボーダー
while (right - left ) != 1:
    mid = round((right+left)/2)
    state = decision(s,td,mid)
    if state < 1:
        left = mid
    else:
        right = mid
if right == N-1:
    right += 1
border_r = right
    
left = 0
right = N-1
#左側のボーダー
while (right - left ) != 1:
    mid = round((right+left)/2)
    state = decision(s,td,mid)
    if state > -1:
        right = mid
    else:
        left = mid
if right == 0:
    right -= 1
border_l = right
print(border_r-border_l)



### FIXED CODE ###

# sys.stdin.readline()
import math
import sys
input = sys.stdin.readline


def decision(s,td,j):
    #index番目の文字が落ちるかどうかを判別
    #右に落ちるときは1，左に落ちるときは-1，落ちないときは0を返す
    global N,Q
    for [qi,v] in td:
        if j < 0 or j >= N:
            break
        if s[j] == qi:
            if v == 'L':
                j -= 1
            else:
                j += 1
    if j == -1:
        return -1
    elif j == N:
        return 1
    else:
        return 0
 
N,Q = map(int,input().split())
s = input()
td = [input().split() for _ in range(Q)]
    
#td[i][j]:i番目の文字(j=0)と方向(j=1)
    
    
RN = math.ceil(math.log2(N))
#2分探索
left = 0
right = N-1
#右側のボーダー
for i in range(RN):
    mid = (right+left)//2
    state = decision(s,td,mid)
    if state < 1:
        left = mid
    else:
        right = mid
    if (right - left) == 1:
        break
if right == N-1 and decision(s,td,right) == 0:
    right += 1
border_r = right
    
left = 0
right = N-1
#左側のボーダー
for i in range(RN):
    mid = ((right+left)//2)
    state = decision(s,td,mid)
    if state > -1:
        right = mid
    else:
        left = mid
    if (right - left) == 1:
        break
if left == 0 and decision(s,td,left) == 0:
    right -= 1
border_l = right
print(border_r-border_l)
### BUGGY CODE ###

def bound2(a,y,x):
  ok=-1
  ng=len(a)
  while ng-ok>1:
    mid=(ok+ng)//2
    if a[mid]*y<=x:ok=mid
    else:ng=mid
  return ok
def bound1(x):
  s=t=0
  for y in a:
    s+=bound2(b,y,x)+1
    t+=bound2(a,y,x)
    if y*y>x:t+=1
  s+=t//2
  t=0
  for y in c:
    t+=bound2(c,y,x)
    if y*y>x:t+=1
  return s+t//2
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bound2(t,1,0)+1
a,b,c=t[i:],t[:i],t[i-1::-1]
ok=10**18+1
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if bound1(mid)>=k:ok=mid
  else:ng=mid
print(ok)

### FIXED CODE ###

from bisect import*
def solve(x):
  s=t=0
  i=n
  j=-1
  for y in a:
    while i and a[i-1]*y>x:i-=1
    while j+1<m and b[j+1]*y<=x:j+=1
    s+=j+1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  t=0
  i=m
  for y in c:
    while i and c[i-1]*y>x:i-=1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  return s
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bisect(t,0)
a,b,c=t[i:],t[:i],t[i-1::-1]
n,m=len(a),len(b)
ok=10**18
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if solve(mid)>=k:ok=mid
  else:ng=mid
print(ok)
### BUGGY CODE ###

N = int(input())
s = [list(input().split( )) for i in range(N)]
#print(s[1][0])
t = sorted(s, key=lambda x:int(x[1]))
#print(t)
count = 0
for i in range(len(t)):
  sum_i = sum([int(t[j][0]) for j in range(0, i+1)])
  if int(t[i][1]) < sum_i :
    count += 1
if count != 0:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

N = int(input())
s = [list(input().split( )) for i in range(N)]
#print(s[1][0])
t = sorted(s, key=lambda x:int(x[1]), reverse = True)
#print(t)
count = 0
sum1 = sum([int(t[j][0]) for j in range(len(t))])
for i in range(len(t)):
  if int(t[i][1]) >= sum1 :
    sum1 = sum1 - int(t[i][0])
  else:
    count += 1
    sum1 = sum1 - int(t[i][0])
if count == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

n, k = map(int, input().split())
arr = [int(x) for x in input().split()]
dp = [float('inf')] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[j] + abs(arr[i] - arr[j]) for j in range(max(i - k, 0), i))
print(dp[n - 1])


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0

    for i in range(1, n):
        d[i] = min(
            d[j] + abs(h[i] - h[j]) for j in range(max(i - k, 0), i)
        )
    return d[n - 1]


print(frog(n, k, h))
### BUGGY CODE ###

import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
S = {}
roads = set()
for i in range(h):
    s = input()
    for j in range(w):
        S[i, j] = s[j]
        if s[j] == '.':
            roads.add((i, j))

reached = {k: False for k in roads}
distance = {v: math.inf for v in roads}
distance[c] = 0
reached = {k: False for k in roads}
queue = deque([c])

while queue:
    u = queue.popleft()
    reached[u] = True
    i, j = u
    adj = []
    if i > 0 and S[i - 1, j] == '.':
        adj.append((i-1, j))
    if j > 0 and S[i, j - 1] == '.':
        adj.append((i, j - 1))
    if i < h-1 and S[i + 1, j] == '.':
        adj.append((i+1, j))
    if j < w-1 and S[i, j+1] == '.':
        adj.append((i, j+1))
    for v in adj:
        if not reached[v]:
            distance[v] = distance[u]
            queue.appendleft(v)

    warp = product(range(max(i-2, 0), min(i+3, h)),
                   range(max(j-2, 0), min(j+3, w)))
    for wa in warp:
        if wa != u and wa not in adj and S[wa] == '.' and not reached[wa]:
            distance[wa] = distance[u] + 1
            queue.append(wa)

print(distance[d] if distance[d] != math.inf else -1)



### FIXED CODE ###

import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])
pathes = {(0, -1), (-1, 0), (0, 1), (1, 0)}
warps = set(product(range(-2, 3), range(-2, 3))) - {(0, 0)} - pathes

while queue:
    i, j = queue.popleft()
    for pi, pj in pathes:
        u, v = i+pi, j+pj
        if 0 <= u < h and 0 <= v < w and S[u][v] == '.' and distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u, v))

    for wi, wj in warps:
        x, y = i + wi, j + wj
        if 0 <= x < h and 0 <= y < w and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x, y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)
### BUGGY CODE ###

from collections import Counter
import math

cmb2 = [0] * 200001
for n in range(2, 200001):
    num = 1
    r = 2
    for i in range(1, r + 1):
        num = num * (n - i + 1) // i
    cmb2[n] = num

n = int(input())
a = list(map(int, input().split()))
nn = len(a) - 1
ctr = Counter(a)

for aa in a:
    x = 0
    for k, v in ctr.items():
        if k == aa:
            v -= 1
        if v >= 2:
            x += cmb2[v]
    print(x)


### FIXED CODE ###

from collections import Counter
import math

n = int(input())
aa = list(map(int, input().split()))

ctr = Counter(aa)

cmb2 = [0] * 200001
for n in range(2, 200001):
    r = 2
    num = 1
    for i in range(1, r + 1):
        num = num * (n - i + 1) // i
    cmb2[n] = num

x = 0
for k, v in ctr.items():
    x += cmb2[v]

for a in aa:
    k = ctr[a] - 1
    print(x - k)
### BUGGY CODE ###

N, M = map(int, input().split())
Ao = list(map(int, input().split()))
A = list(sorted(Ao))
for j in range(M):
    B, C = map(int, input().split())
    for i in range(B):
        if A[i] < C:
            A.remove(A[i])
            A.insert(i,C)
    A = list(sorted(A))

print(sum(A))

### FIXED CODE ###


N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
D = []
for j in range(M):
    B, C = map(int, input().split())
    D.append((B,C))
#list is sorted by C in D
D = sorted(D, key = lambda x: x[1], reverse = True) 

i = 0
for j in range(M):
    b, c = D[j]
    for k in range(i, min(N, i+b)):
        if A[k] < c:
            A[k] = c
    i = i + b
print(sum(A))
### BUGGY CODE ###

import itertools
s = input()
K = int(input())
table = {}
for i, j in itertools.combinations(range(len(s) + 1), 2):
    table[s[i : j]] = 1
print(sorted(table)[K - 1])

### FIXED CODE ###

import itertools
s = input()
K = int(input())
dp = []

def substr(x):
    table = {}
    for i, j in itertools.combinations(range(len(x) + 1), 2):
        table[x[i:j]] = 1
    return sorted(table.keys())[:5]

dp = []

if len(s) < 6:
    dp = substr(s)
else:
    dp = substr(s[-5:])
    for i in range(-6, -len(s) -1, -1):
        for j in range(1, 6):
            if not s[i : i + j] in dp:
                dp = sorted(dp + [s[i : i + j]])[:5]
print(dp[K - 1])
### BUGGY CODE ###

x,y=map(int,input().split())
MAX_NUM = 2*10**6 + 1
pr = 10**9+7
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
if (x+y)%3:
    print(0)
else:
    n=(x+y)//3
    x-=n
    y-=n
    print(c(x+y,x))


### FIXED CODE ###

x,y=map(int,input().split())
MAX_NUM = 2*10**6 + 1
MAX_NUM//=3
MAX_NUM+=1
pr = 10**9+7
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
if (x+y)%3:
    print(0)
else:
    n=(x+y)//3
    x-=n
    y-=n
    print(c(x+y,x))
### BUGGY CODE ###

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

LR = {}
for i in range(M):
  L, R = map(int, input().split())
  if L in LR:
    LR[L].append(R)
  else:
    LR[L] = [R]

for r in LR.values():
  r.sort()

for i in range(Q):
  p, q = map(int, input().split())
  s = 0
  for l,r in LR.items():
    if not p <= l <= q: continue
    for j in r:
      if q < j: break
      s += 1
  print(s)

### FIXED CODE ###

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

LR = [[0]*(N+2-i) for i in range(N+2)]
for i in range(M):
  L, R = map(int, input().split())
  LR[L][R-L+1] += 1

  
for i in range(2,N+2):
  for j in range(1,N-i+2):
    LR[j][i] += LR[j][i-1] + LR[j+1][i-1] - LR[j+1][i-2]
    
for i in range(Q):
  p, q = map(int, input().split())
  print(LR[p][q-p+1]-LR[q+1][0])
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

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

N = int(readline())
PATH = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7

fact = [0] * (N + 10)
t = 1
for i in range(1, N + 1):
    t *= i
    t %= MOD
    fact[i] = t

for _ in range(N - 1):
    x, y = map(int, readline().split())
    PATH[x].append(y)
    PATH[y].append(x)


@lru_cache(maxsize=None)
def dfs(x, parent, isBlack=True):
    ret = 1
    for v in PATH[x]:
        if v == parent:
            continue

        cnt = dfs(v, x, False)

        if not isBlack:
            cnt += dfs(v, x, True)

        ret *= cnt
        ret %= MOD

    ret %= MOD

    return ret


ans = dfs(1, -1, True) + dfs(1, -1, False)
ans %= MOD
print(ans)


### FIXED CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

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

# TLE

N = int(readline())
PATH = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7

for _ in range(N - 1):
    x, y = map(int, readline().split())
    PATH[x].append(y)
    PATH[y].append(x)


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


def dfs(x, parent):
    for v in PATH[x]:
        if v == parent:
            continue
        dfs(v, x)

        dp[x][0] *= (dp[v][0] + dp[v][1])
        dp[x][0] %= MOD
        dp[x][1] *= dp[v][0]
        dp[x][1] %= MOD

    return 0


dfs(1, -1)
ans = sum(dp[1])
ans %= MOD
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
*V, = map(int, input().split())
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | (A[i] << V[i])) & MASK
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i])) & MASK

ans = N
for i in range(N):
    a = A[i]; b = B[i+1]
    t = K
    r = 0
    for s in range(K+1):
        if a & 1 == 0:
            a >>= 1
            continue
        while t > -1 and (s + t >= K or b & 1 == 0):
            t -= 1
            b >>= 1
        if t == -1:
            break
        r = max(r, s + t)
        a >>= 1
    if K-V[i] <= r < K:
        ans -= 1
print(ans)


### FIXED CODE ###

import random
N, K = map(int, input().split())
*V, = map(int, input().split())
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | ((A[i] << V[i]) & MASK))
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i]))

ans = N
for i in range(N):
    if K <= V[i]:
        ans -= 1
        continue
    a = A[i]; b = B[i+1]
    VM = 2**(V[i]+1)-2
    l = 1
    while a and b and l:
        if a & 1 and b & VM:
            ans -= 1
            break
        l = max((a & -a).bit_length()-1, (b & -b).bit_length()-V[i]-1)
        a >>= l; b >>= l
print(ans)
### BUGGY CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

ans = 0
for i in range(n):
    if i <= n - k:
        ans -= a[i] * combinations_count(n-i-1, k-1)
    
    if i >= k - 1:
        ans += a[i] * combinations_count(i, k-1)
    
print(ans % (10 ** 9 + 7))

### FIXED CODE ###

def prepare(n, MOD):
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

def combinations_count(n, r, factorials, invs):
    return (factorials[n] * invs[n-r] * invs[r]) % (10 ** 9 + 7)
 
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))

factorials, invs = prepare(n, 10 ** 9 + 7)

ans = 0
for i in range(n):
    if i <= n - k:
        ans -= a[i] * combinations_count(n-i-1, k-1, factorials, invs)
    
    if i >= k - 1:
        ans += a[i] * combinations_count(i, k-1, factorials, invs)
    
    ans = ans % (10 ** 9 + 7)
 
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N, M, K = map(int, input().split())
edges = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].add(b)
    edges[b].add(a)

block_edges = [set() for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    block_edges[c].add(d)
    block_edges[d].add(c)

visited = [False] * N
cnt = 0

def dfs(u, s):
    if visited[u]:
        return

    visited[u] = True
    for v in edges[u]:
        if visited[v]:
            continue
        if v == s:
            continue

        if v in block_edges[s] or v in edges[s]:
            pass
        else:
            global cnt
            cnt += 1

        dfs(v, s)


ans = []
for i in range(N):
    visited = [False] * N
    cnt = 0
    for v in edges[i]:
        dfs(v, i)
    ans.append(cnt)
print(*ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.d = [-1] * n

    def find(self, x):
        if self.d[x] < 0:
            return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.d[self.find(x)]


N, M, K = map(int, input().split())
NMAX = 100005
deg = [0] * NMAX
to = [[] for _ in range(NMAX)]
uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
anss = []
for i in range(N):
    ans = uf.size(i) - 1 - deg[i]
    for u in to[i]:
        if uf.same(i, u):
            ans -= 1
    anss.append(ans)
print(" ".join(map(str, anss)))