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

def lcsLength(s, t):
    n = len(s) + 1
    m = len(t) + 1
    c = [[-1] * (m) for x in [-1] * (n)]
    direction = [[-1] * (m) for x in [-1] * (n)]
    for i in range(n):
        c[i][0] = 0
    for j in range(m):
        c[0][j] = 0
    for i in range(1, n):
        for j in range(1, m):
            if s[i - 1] == t[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
                direction[i][j] = 0 # volta uma linha e uma coluna
            elif c[i][j - 1] >= c[i - 1][j]:
                c[i][j] = c[i][j - 1]
                direction[i][j] = 1 # volta uma coluna na mesma linha
            else:
                c[i][j] = c[i - 1][j]
                direction[i][j] = 2 # volta uma linha na mesma coluna
    return direction

def getLCS(direction, s, i, j, lcs=""):
    if i == 0 or j == 0:
        return lcs
    if direction[i][j] == 0: # volta uma linha e uma coluna
        lcs += getLCS(direction, s, i - 1, j - 1, lcs)
        lcs += s[i - 1]
        return lcs
    elif direction[i][j] == 2: # volta uma linha na mesma coluna
        lcs += getLCS(direction, s, i - 1, j, lcs)
    else: # volta uma coluna na mesma linha
        lcs += getLCS(direction, s, i, j - 1, lcs)
    return lcs

s = input()
t = input()
d = lcsLength(s, t)
print(getLCS(d, s, len(d) - 1, len(d[0]) - 1))

### FIXED CODE ###

s = input()
t = input()

m = len(s)
n = len(t)

dp = [[None] * (n+1) for i in range(m+1)]

for i in range(m+1):
    for j in range(n+1):

        if i == 0 or j == 0:
            dp[i][j] = 0

        elif s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1

        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])



final = dp[m][n]

lcs = [""] * (final + 1)
lcs[final] = ""

i = m
j = n

while i > 0 and j > 0:
    if s[i-1] == t[j-1]:
        lcs[final-1] = s[i-1]
        i -= 1
        j -= 1
        final -= 1

    elif dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1


print("".join(lcs))
### BUGGY CODE ###

n=int(input())
o=0
for i in range(n):
  for j in range(n-i):
    if (i+1)+(i+1+j+1)==n:
      o=o+1
      
print(o)

### FIXED CODE ###

n=int(input())
if n%2==0:
  o=int(n/2-1)
else:
  o=int((n-1)/2)
      
print(o)
### BUGGY CODE ###

n = int(input())
s = []
ans = 0
for _ in range(n):
  x = list(input())
  x.sort()
  s.append("".join(x))
for i in range(n):
  for j in range(i+1, n):
    if s[i]==s[j]:
      ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
b = {}
ans = 0
for _ in range(n):
  x = list(input())
  x.sort()
  x = "".join(x)
  if not x in b:
    b[x] = 0
  else:
    b[x] += 1
    ans += b[x]
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if j - i != k - j:
                if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
r, g, b = 0, 0, 0
for s in S:
    if s == 'R':
        r += 1
    elif s == 'G':
        g += 1
    else:
        b += 1
ans = r * g * b
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = 2 * j - i
        if k < N:
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1
print(ans)
### BUGGY CODE ###

from fractions import gcd
import sys

def main():
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = a[0]

    #mmm=10**9+7
    for i in range(1, n):
        ans = ans * a[i] // gcd(ans, a[i])

    result=0
    for item in a:
      result=(result+ans//item)%(10**9+7)

    print(result)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = 1

    mmm=10**9+7
    for i in a:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

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

K = int(input())
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += (gcd(i,j,k))
print(ans)

### FIXED CODE ###

K = int(input())
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


temp = []

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            temp.append(gcd(i,j,k))
print(sum(temp))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []

for i in range(1, n+1):
  b.append(a.index(i)+1)
  
  
print(" ".join(map(str, b)))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
d=[0]*n
for i,val in enumerate(l):
  d[val-1]=i+1
print(*d)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
setA = set(A)
B = len([A.count(i) for i in setA if A.count(i) % 2 != 0])
print(B)

### FIXED CODE ###

N = int(input())
A = {}
for i in range(N):
    a = int(input())
    A.setdefault(a, 0)
    if a in A:
        A[a]+=1
count = 0
for v in A.values():
    if v%2!=0:
        count += 1
print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
H = []
for i in range(N):
    H.append(int(input()))

H = sorted(H)
min_diff = float('inf')
for i in range(N-K+1):
    trees = H[i:i+K]
    diff = trees[-1] - trees[0]
    if diff < min_diff:
        min_diff = diff
print(min_diff)


### FIXED CODE ###

N, K = map(int, input().split())
H = []
for i in range(N):
    H.append(int(input()))

H = sorted(H)
min_diff = float('inf')
for i in range(0, N-K+1):
    diff = H[i+K-1] - H[i]
    if diff < min_diff:
        min_diff = diff
print(min_diff)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N, a, b = map(int, input().split())
    S = str(input())
    A, B = [0] * N, [0] * N
    for i in range(N):
        if S[i] == 'a':
            A[i] = 1
        elif S[i] == 'b':
            B[i] = 1
    from itertools import accumulate

    AA = [0] + A
    AA = list(accumulate(AA))  # 累積和を格納したリスト作成
    BB = [0] + B
    BB = list(accumulate(BB))  # 累積和を格納したリスト作成

    for i in range(N):
        if S[i] == 'a':
            if AA[i + 1] + BB[i + 1] - 1 < a + b:
                print('Yes')
            else:
                print('No')
                for j in range(i + 1, N + 1):
                    AA[j] -= 1
        elif S[i] == 'b':
            if AA[i + 1] + BB[i + 1] - 1 < a + b and BB[i + 1] - 1 < b:
                print('Yes')
            else:
                print('No')
                for j in range(i + 1, N + 1):
                    BB[j] -= 1

        else:
            print('No')


resolve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N, a, b = map(int, input().split())
    S = str(input())
    cnta=0
    cntb=0

    for i in range(N):
        if S[i] == 'a':
            if cnta + cntb < a + b:
                print('Yes')
                cnta+=1
            else:
                print('No')
        elif S[i] == 'b':
            if cnta + cntb < a + b and cntb < b:
                print('Yes')
                cntb+=1
            else:
                print('No')

        else:
            print('No')


resolve()
### BUGGY CODE ###

import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n = ni()
a = na()

def gcd(m, n):
    if n == 0:
        return m
    return gcd(n, m % n)

def lcm(m, n):
    return m * n // gcd(m, n)

l = a[0]
for i in range(n):
    l = lcm(a[i], l)
ans = 0
for i in range(n):
    ans += l // a[i]
    ans = ans % 1000000007

print(ans)

### FIXED CODE ###

import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n = ni()
a = na()

def gcd(m, n):
    if n == 0:
        return m
    return gcd(n, m % n)

def lcm(m, n):
    return m * n // gcd(m, n)

l = a[0]
for i in range(n):
    l = lcm(a[i], l)
ans = 0
for i in range(n):
    ans += l // a[i]

ans %= 1000000007
print(ans)
### BUGGY CODE ###

a,b,c = map(int, input().split())
k = int(input())
 
i = 0
while i < k:
  if a < b < c:
    break
  elif a >= b:
    b = b * 2
    i += 1
    if c >= b:
      c = c * 2
      i += 1
 
if a < b < c:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a,b,c = map(int, input().split())
k = int(input())
 
i = 0
while a >= b:
  b = b * 2
  i += 1

j = 0
while b >= c:
  c = c * 2
  j += 1
  
if i + j <= k:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

import fractions
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
ans = 0
lcm_half = A[0]//2
flag = 0
numofdiv2 = 0
for s in range(A[0]):
    if A[0] % 2 == 0:
        numofdiv2 += 1
        A[0] //= 2
    else:
        break
for i in range(1, N):
    for k in range(A[i]):
        if A[i] % (2**numofdiv2) != 0 or A[i] % (2**(numofdiv2+1)) == 0:
            flag = 1
            break
    gcd = fractions.gcd((A[i] // 2), lcm_half)
    lcm_half = (lcm_half * (A[i] // 2)) // gcd
    if lcm_half > M:
        flag = 1
        break
if flag == 1:
    ans = 0
else:
    M -= lcm_half
    ans = 1+M//(lcm_half*2)
# print(lcm_half)
print(ans)


### FIXED CODE ###

import fractions
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
ans = 0
lcm_half = A[0]//2
flag = 0
numofdiv2 = 0
for s in range(A[0]):
    if A[0] % 2 == 0:
        numofdiv2 += 1
        A[0] //= 2
    else:
        break

for i in range(1, N):

    if A[i] % (2**numofdiv2) != 0 or A[i] % (2**(numofdiv2+1)) == 0:
        flag = 1
        break
    gcd = fractions.gcd((A[i] // 2), lcm_half)
    lcm_half = (lcm_half * (A[i] // 2)) // gcd
    if lcm_half > M:
        flag = 1
        break
if flag == 1:
    ans = 0
else:
    M -= lcm_half
    ans = 1+M//(lcm_half*2)
# print(lcm_half)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.buffer.readline
def inp():
    return map(int,input().split())
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = inp()
    e[a-1].append(b-1)
    e[b-1].append(a-1)

p = [0] * n
for _ in range(q):
    pp, x = inp()
    p[pp - 1] += x


def dfs(i=0, r=-1):
    for j in e[i]:
        if j != r:
            p[j] += p[i]
            dfs(j, i)
dfs()

print(*list(map(str,p)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))
### BUGGY CODE ###

N = input()
a = input().split()
ans = 1
for i in a:
    ans *= int(i)
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

def aaa(a_list):
    ans = 1
    for i in a_list:
        ans = ans * i
        if ans > 10**18:
            return -1
    return ans

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

if 0 in a:
    print(0)
else:
    print(aaa(a))
### BUGGY CODE ###

def main():
    platform_count, jumping_power = [int(x) for x in input().split()]
    platforms = [int(x) for x in input().split()]
    INF = 10001
    dp = [INF] * platform_count
    dp[0] = 0
    for i in range(1, platform_count):
        indexes = (i - x for x in range(1, jumping_power + 1) if i - x >= 0)
        dp[i] = min(
            abs(platforms[i] - platforms[before]) + dp[before]
            for before in indexes)
    print(dp[platform_count - 1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    platform_count, jumping_power = [int(x) for x in input().split()]
    platforms = [int(x) for x in input().split()]
    dp = [0]
    for i in range(1, platform_count):
        indexes = (i - x for x in range(1, jumping_power + 1) if i - x >= 0)
        dp.append(
            min(abs(platforms[i] - platforms[before]) + dp[before]
                for before in indexes))
    print(dp[platform_count - 1])


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

# N = map(int,input().split())
# HRR = list(map(int,input().split()))

# N, K = 3,1
# HRR = [10, 20, 10]
#
# N,K = 10, 4
# HRR = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]

N,K = map(int,input().split())
HRR = list(map(int,input().split()))

def calculate(n, k, hrr):
    result = []
    for index, value in enumerate(hrr):
        srr = []
        for j in range(1, k + 1):
            if index - j >= 0:
                srr.append(result[index - j] + abs(hrr[index] - hrr[index - j]))

        if len(srr) == 0:
            result.append(0)
        else:
            result.append(min(srr))

    print(result[-1])

calculate(N, K, HRR)


### FIXED CODE ###

# N, K = 5, 3
# HRR = [10, 30, 40, 50, 20]

N, K = 3, 1
HRR = [10, 20, 10]

N, K = 2, 100
HRR = [10, 10]

N, K = 10, 4
HRR = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]

N, K = map(int, input().split())
HRR = list(map(int, input().split()))


def calculate(n, k, hrr):
    result = []
    for i in range(n):
        if i == 0:
            result.append(0)
            continue

        mins = -1
        for j in range(1, k + 1):
            index = i - j
            if index >= 0:
                value = result[index] + abs(hrr[i] - hrr[index])
                if mins == -1:
                    mins = value
                else:
                    if value < mins:
                        mins = value
        result.append(mins)

    print(result[-1])


calculate(N, K, HRR)
### BUGGY CODE ###

# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
    #print(xytuple)
  return mlength


#X = str(input()).split()
HW = str(input()).split()
H = int(HW[0])
W = int(HW[1])
S = [[0 for i in range(W)] for j in range(H)]
# SS = [[INF]*(W*H)]*(W*H)
mlength = 0


for i in range(H):
  temp = str(input())
  for j in range(W):
    #print(i,j)
    S[i][j]=temp[j]


for i in range(H):
  for j in range(W):
    if(S[i][j] != "#"):
      TS = copy.deepcopy(S)
      mlength = max(mlength, bfs(TS, i, j, H, W))
    #print(S)

print(mlength);


### FIXED CODE ###

# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
HW = str(input()).split()
H = int(HW[0])
W = int(HW[1])
S = [[0 for i in range(W)] for j in range(H)]
# SS = [[INF]*(W*H)]*(W*H)
mlength = 0


for i in range(H):
  temp = str(input())
  for j in range(W):
    S[i][j]=temp[j]


for i in range(H):
  for j in range(W):
    if(S[i][j] != "#"):
      TS = copy.deepcopy(S)
      mlength = max(mlength, bfs(TS, i, j, H, W))

print(mlength);
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
R=set(L)
ans=0
for i in R:
  c=L.count(i)
  if c<i:
    ans+=c
  else:
    ans+=c-i
print(ans)

### FIXED CODE ###

from collections import Counter
N=int(input())
L=list(map(int,input().split()))
ke=list(Counter(L).values())
val=list(Counter(L).keys())
ans=0
for i in range(len(val)):
  if val[i]>ke[i]:
    ans+=ke[i]
  else:
    ans+=ke[i]-val[i]
print(ans)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
S = list(input())
a = set()
for data in combinations(S, 3):
    a.add(''.join(data))
print(len(a))

### FIXED CODE ###

N = int(input())
S = input()

count = 0
numberlist = [str(i) for i in range(10)]

for a in numberlist:
    idx1 = S.find(a)
    if idx1 == -1 or idx1 >= N - 2:
        continue
    
    for b in numberlist:
        idx2 = S[idx1+1:].find(b)
        if idx2 == -1 or idx2 >= N - 1:
            continue

        count += len(set(S[idx1+idx2+2:]))

print(count)
### BUGGY CODE ###

n=int(input())
plan=[None]*n
for i in range(n):
  p=list(map(int,input().split()))
  for j in range(len(p)):
    p[j]=p[j]-1
  plan[i]=p

d=0
error=False
while True:
  d=d+1
  done=[True]*n
  thisday=False
  for i in range(n):
    if done[i]==False:
      continue
    if len(plan[i])==0:
      continue
    target=plan[i][0]
    if done[target]==False:
      continue
    if len(plan[target])==0:
      continue
    if plan[target][0]==i:
      # match
      plan[i].pop(0)
      plan[target].pop(0)
      done[i]=False
      done[target]=False
      thisday=True
  if thisday==False:
    # no game today
    # check if every plan is finished
    for i in range(len(plan)):
      if len(plan[i])!=0:
        error=True
    break
  
if error:
  print(-1)
else:
  print(d-1)

### FIXED CODE ###

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

X = int(input())

A = 0
while True:
    n = X - A**5
    B = int(A**(1/5))
    if B ** 5 == n:
        print(A, -B)
        break
    B += 1
    if B ** 5 == n:
        print(A, -B)
        break
    A += 1

### FIXED CODE ###

X = int(input())

A = 0
while True:
    n = X - A ** 5
    if n == 0:
        print(A, 0)
    elif n > 0:
        B = int(n ** (1 / 5))
        if B ** 5 == n:
            print(A, -B)
            break
        B += 1
        if B ** 5 == n:
            print(A, -B)
            break
        A += 1
    else:
        B = - int((-n) ** (1 / 5))
        if B ** 5 == n:
            print(A, -B)
            break
        B -= 1
        if B ** 5 == n:
            print(A, -B)
            break
        A += 1
### BUGGY CODE ###

import numpy as np
n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
con = [1 for _ in range(n+1)]
uni = np.array([-1 for i in range(n+1)])

def root(num, pea, index=True):
    get_index = []
    while pea[num] > 0:
        get_index.append(num)
        num = pea[num]
    if index:
        return num, get_index
    else:
        return num

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a, get_a_index = root(a, uni)
        root_b, get_b_index = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[get_a_index+get_b_index+[root_b]] = root_a

for i in range(k):
    c, d = cd[i]
    if root(c, uni, index=False) == root(d, uni, index=False):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni, index=False)
    result.append(-uni[root_i]-con[i])
print(*result)

### FIXED CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
con = [1 for _ in range(n+1)]
uni = UnionFind(n+1)


for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    uni.Unite(a, b)

for i in range(k):
    c, d = cd[i]
    if uni.isSameGroup(c,d):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    result.append(uni.Count(i)-con[i])
print(*result)
### BUGGY CODE ###

N=int(input())
l=list(map(int,input().split()))
l.sort()
count=0

for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if l[i]+l[j]>l[k]:
                count+=1
            else:
                break
print(count)

### FIXED CODE ###

N=int(input())
l=list(map(int,input().split()))
l.sort()
count=0
import bisect
for i in range(N):
    for j in range(i+1,N-1):
        m=bisect.bisect_left(l,l[i]+l[j])
        count+=m-(j+1)
print(count)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for i in range(N//R+1):
    for j in range(N//G+1):
        b = N - R*i - G*j
        if(b >= 0 and b%B == 0):
            cnt += 1
print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for i in range(N//R+1):
    for j in range(N//G+1):
        b = N - R*i - G*j
        if(b < 0):
            break
        if(b%B == 0):
            cnt += 1
print(cnt)