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

from collections import deque
import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]
 
# フレンドの隣接リスト
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)
 
# ブロックの隣接リスト
for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)
 
 
# 交友関係グループ（辞書型）
D = {}
# グループの親
parent = [-1] * N
# 訪問管理
visited = [False] * N
stack = deque()
 
for root in range(N):
    if visited[root]:
        continue
 
    D[root] = set([root])
    # 訪問先のスタック
    stack.append(root)
    # 訪問先が無くなるまで
    while len(stack)>0:
        # 訪問者をポップアップ
        n = stack.popleft()
        if visited[n]:
            continue
        # 訪問者を訪問済み
        visited[n] = True
        # 訪問者のグループの親を設定
        parent[n] = root
 
        # root のフレンドをグループと訪問先に追加
        D[root]=D[root] | set(F[n])
        stack.extend(F[n])
 
ans = [0] * N
for iam in range(N):
    # 自分の交友関係グループを設定
    group = D[parent[iam]]
    # グループからフレンドと自分を除く
    tmp_ans = len(group) - len(F[iam]) - 1
    # グループからブロックを除く
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans
 
print(*ans, sep=' ')

### FIXED CODE ###

from collections import deque

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

cango = [[]for i in range(n)]
cannotgo=[[]for i in range(n)]
for i in range(m):
    a,b = (map(int,input().split()))
    a,b = a-1,b-1
    cango[a].append(b)
    cango[b].append(a)

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c].append(d)
    cannotgo[d].append(c)
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}
y = deque()
# print(gro)
for i in range(n):
    # if alre[i]==True:
    #     continue
    # gro[i]=set([i])
    y.append(i)
    leader = i
    cnt = 0 
    while len(y)>0:
        x = y.popleft()
        if parent[x]!=-1:
            continue
            # print(to)
        parent[x]=leader
        y.extend(cango[x])
        cnt +=1
    if cnt!=0:
        gro[leader]=cnt
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    # group = gro[parent[iam]]
    tmp_ans = gro[parent[iam]]
    tmp_ans -=1
    tmp_ans -= len(cango[iam])
    for block in cannotgo[iam]:
        if parent[block]==parent[iam] :
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')
### BUGGY CODE ###

import sys
N = int(input())
L = [i for i in map(int,input().split()) if i%2 == 0]
even = 1
j = 0
if L == []:
  print(0)
  sys.exit(0)
for i in range(len(L)):
  even *= L[i]
while (even % 2**j == 0):
  j += 1
print(j-1)


### FIXED CODE ###

import sys
import numpy
N = int(input())
L = [i for i in map(int,input().split()) if i%2 == 0]
L2 = [0 for i in range(len(L))]
if L == []:
  print(0)
  sys.exit(0)
for i in range(len(L)):
    s = 1
    while L[i] % 2**s == 0:
        s += 1
    L2[i] = s-1
Q = numpy.sum(L2)
print(Q)
### BUGGY CODE ###

l=list(input())
count=0
while True:
    flag=True
    for i in range(len(l)-1):
        if l[i]!=l[i+1]:
            l.pop(i)
            l.pop(i)
            flag=False
            count+=2
        if i>=len(l)-2:
            break
    if flag:
        break
print(count)


### FIXED CODE ###

l=list(input())
o=0
z=0
for i in range(len(l)):
    if l[i]=="0":
        z+=1
    elif l[i]=="1":
        o+=1

if z > o:
    print(2*o)
else:
    print(2*z)
### BUGGY CODE ###

#!/usr/bin/env python3

# input
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
for i in range(n):
    p[i] -= 1

# calc
ans = -int(1e18)
for si in range(n):
    x = si
    s = []
    opscore = 0 
    while True:
        x = p[x]
        opscore += c[x]
        s.append(c[x])
        if x == si: 
            break

    oplen = len(s)
    t = 0 
    for i in range(oplen):
        t += s[i]
        if i+1 > k:
            break
        now = t 
        if opscore > 0:
            e = (k-(i+1))//oplen
            now += opscore * e 
        ans = max(ans, now)

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

# input
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
for i in range(n):
    p[i] -= 1

# calc
ans = -int(1e18)
for si in range(n):
    x = si
    s = []
    opscore = 0 
    while True:
        x = p[x]
        opscore += c[x]
        s.append(c[x])
        if x == si: 
            break

    oplen = len(s)
    t = 0 
    for i in range(oplen):
        t += s[i]
        if i+1 > k:
            break
        now = t 
        if opscore > 0:
            e = (k-(i+1))//oplen
            now += opscore * e 
        ans = max(ans, now)

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

r1,c1,r2,c2=map(int,input().split())

mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

def F(r,c):
  ans=0
  for i in range(r+c+1):
    ans+=pow(2,i,mod)
    ans%=mod
  d=0
  s=0
  for i in range(r-1,-1,-1):
    s+=comb((r-i-1)+c,c)
    d+=pow(2,i,mod)*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  d=0
  s=0
  for i in range(c-1,-1,-1):
    s+=comb((c-i-1)+r,r)
    d+=pow(2,i,mod)*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  return ans

ans=F(r2,c2)
ans=(ans+(mod-F(r2,c1-1)))%mod
ans=(ans+(mod-F(r1-1,c2)))%mod
ans+=F(r1-1,c1-1)
print(ans%mod)


### FIXED CODE ###


p = 10**9+7
kai_ = [1]
for i in range(1, 10 ** 7):
    kai_.append(kai_[-1] * i % p)


def kai(x):
    return kai_[x]


def comb(a, b):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a)
    c *= pow(kai(b), p - 2, p)
    c *= pow(kai(a - b), p - 2, p)
    return c % p


r1, c1, r2, c2 = [int(i) for i in input().split()]


def s(r, c):
    return comb(r+c+2,r+1)


print((s(r2, c2) - s(r2, c1 - 1) - s(r1 - 1, c2) + s(r1 - 1, c1 - 1)) % p)
### BUGGY CODE ###

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

N, M = map(int, input().split())
# 0段目からN段目まである
N += 1
broken_stairs = [int(input()) for _ in range(M)]

# dp[i] = i段目に辿り着くまでの経路本数
dp = [0 for _ in range(N)]

# 初期値
dp[0] = 1

# MOD用
MOD = 10 ** 9 + 7

for i in range(N):
    # 1段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 1 < N and i + 1 not in broken_stairs:
        # MODを取って更新
        dp[i + 1] += dp[i] % MOD
    # 2段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 2 < N and i + 2 not in broken_stairs:
        # MODを取って更新
        dp[i + 2] += dp[i] % MOD

print(int(dp[-1] % MOD))


### FIXED CODE ###

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

N, M = map(int, input().split())
# 0段目からN段目まである
N += 1
broken_stairs = [int(input()) for _ in range(M)]

# dp[i] = i段目に辿り着くまでの経路本数
dp = [1 for _ in range(N)]

# 初期化する
for b in broken_stairs:
    dp[b] = 0

# MOD用
MOD = 10 ** 9 + 7

for i in range(2, N):
    """TLEだったやつ
    # 1段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 1 < N and i + 1 not in broken_stairs:
        # MODを取って更新
        dp[i + 1] += dp[i] % MOD
    # 2段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 2 < N and i + 2 not in broken_stairs:
        # MODを取って更新
        dp[i + 2] += dp[i] % MOD
    """
    # i段目が使用可能なら1段前と2段前の経路数を足した値を入れる
    if dp[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


print(dp[-1])
### BUGGY CODE ###

n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
p = 10**9+7
DP = [0 for s in range(1 << n)]
DP[0] = 1
for s in range(1, 1 << n):
    l = bin(s).count('1')
    for i in range(n):
        if ((1 << i) & s) * A[l-1][i]:
            DP[s] += DP[~(1 << i) & s]
            DP[s] %= p
print(DP[(1 << n)-1])


### FIXED CODE ###

def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    p = 10**9+7
    DP = [0 for s in range(1 << n)]
    DP[0] = 1
    for s in range(1, 1 << n):
        l = bin(s).count('1')
        for i in range(n):
            if ((1 << i) & s) * A[l-1][i]:
                DP[s] += DP[~(1 << i) & s]
    print(DP[(1 << n)-1] % p)


main()
### BUGGY CODE ###

N = int(input())
btn = [int(input())-1 for _ in range(N)]
i = 0
li = [0]

for _ in range(N):
    k = btn[i]
    #print(k, li)
    if k in li:
        print('-1')
        break
    else:
        if k != 1:
            li.append(k)
        else:
            print(len(li))
            break
    i = k

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    btn = [int(input())-1 for _ in range(N)]
    i = 0
    li = [False]*N
    #print(btn)
    
    for _ in range(N):
        li[i] = True
        k = btn[i]
        
        #print(k, li)
        if li[k]:
            print('-1')
            break
        elif k == 1:
            print(sum(li))
            break
        
        i = k
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

ans = 1
for ll in l:
  ans *= ll
  
if ans > 10**18:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

N = int(input())
l = sorted(list(map(int, input().split())))

ans = 1
for ll in l:
  ans *= ll
  if ans > 10**18 or ans==0:
    break
  
if ans > 10**18:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
ai = []
bi = []
for i in range(n):
    ai.append(n - bisect.bisect_right(b, a[i]))
    bi.append(n - bisect.bisect_right(c, b[i]))
ans = 0
for j in ai:
    ans += sum(bi[n-j:])
print(ans)

### FIXED CODE ###

from itertools import accumulate
import bisect
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
b.sort()
c.sort()
ai = []
bi = []
for i in range(n):
    ai.append(n - bisect.bisect_right(b, a[i]))
    bi.append(n - bisect.bisect_right(c, b[i]))
ans = 0
c = [0]+list(accumulate(bi[::-1]))
for j in ai:
    ans += c[j]
print(ans)
### BUGGY CODE ###

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

m = (n-1) // 2
 
x_sorted = sorted(x)

for i in range(n):
    ind = x_sorted.index(x[i])
    print((x_sorted[0:ind] + x_sorted[ind+1:])[m])

### FIXED CODE ###

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

sorted_x = sorted(x)
l = sorted_x[n//2]
s = sorted_x[n//2-1]

for i in x:
    if i <= s:
        print(l)
    else:
        print(s)
### BUGGY CODE ###

import re
a=int(input())
b=str(input())
sum=0
c=b
d=b
i=0
for s in b:
    for n in range(i,a):
        if c[n]!=c[i]:
            j=n-i
            if a>=n:
                for m in range(n,a):
                    if c[m]!=c[i] and c[m]!=c[n]:
                        k=m-n
                        if k!=j:
                            sum+=1



    i+=1
print(sum)

### FIXED CODE ###

a=int(input())
b=str(input())
sum=0

riron_sum=b.count('R')*b.count('G')*b.count('B')

for i in range(0,a):
    for n in range(0,a+1):
        j = i+n
        k = j+n
        #print(j)
        #print(k)
        if k>=a:
        	break

        if b[i]!=b[j] and b[j]!=b[k] and b[k]!=b[i]:
                riron_sum-=1

print(riron_sum)
### BUGGY CODE ###

h, ｎ = map(int, input().split())
dp = [-1] * (h + 1)
dp[0]=0
ab = []

for i in range(n):
  temp = list(map(int, input().split()))
  ab.append(temp)

for i in range(h):
  if dp[i] == -1: continue
  for j in ab:
    ht = i + j[0]
    if ht >= h: ht = h
    if dp[ht] != -1:
      dp[ht] = min(dp[ht], dp[i] + j[1])
    else:
      dp[ht] = dp[i] + j[1]

print(dp[h])


### FIXED CODE ###

h, ｎ = map(int, input().split())
dp = [-1] * (h + 1)
dp[0]=0
ab = []

for i in range(n):
  temp = list(map(int, input().split()))
  ab.append(temp)

for i in range(h):
  if dp[i] == -1: continue
  for j in ab:
    ht = i + j[0]
    if ht >= h: ht = h
    if dp[ht] != -1:
      dp[ht] = min(dp[ht], dp[i] + j[1])
    else:
      dp[ht] = dp[i] + j[1]

print(dp[h])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N=input()

#約数列挙
def make_divisors(n):
    divisors=[]
    ret=0
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            ret+=1
            if i!=n/i:
                ret+=1
    return ret

ans=0
for i in range(1,N+1):
    ans+=i*make_divisors(i)
print ans


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
N=input()
A=[ 2 for _ in range(N+1)]
A[0]=0
A[1]=1

for cur in range(2,N+1):
    for i in range(cur*2,N+1,cur):
        A[i]+=1

ans=0
for i in range(1,N+1):
    ans+=i*A[i]
print ans
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def get_descendants(childrens, dc, i):
  if dc[i] is not None:
    return dc[i]
  if childrens[i] is None:
    return []
  dc[i] = []
  dc[i].extend(childrens[i])
  for j in childrens[i]:
    dc[i].extend(get_descendants(childrens, dc, j))
  return dc[i]
n, q = map(int, input().split())
values = [0] * (n + 1)
childrens = [None] * (n + 1)
dc = [None for i in range(0, n + 1)]
for i in range(n - 1):
  a, b = map(int, input().split())
  if childrens[a] is None:
    childrens[a] = []
  childrens[a].append(b)
for _ in range(q):
  p, x = map(int, input().split())
  values[p] += x
  for d in get_descendants(childrens, dc, p):
    values[d] += x
print(*[values[i] for i in range(1, n + 1)])


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
def main():
  _map = map
  _input = input
  _int = int
  def calc_results(results, pvalue, i):
    results[i] = pvalue + values[i]
    for j in childrens[i]:
      calc_results(results, results[i], j)
  n, q = _map(_int, _input().split())
  values = [0] * (n + 1)
  results = [0] * (n + 1)
  childrens = [[] for _ in range(n + 1)]
  for i in range(n - 1):
    a, b = _map(_int, _input().split())
    childrens[a].append(b)
  for _ in range(q):
    p, x = _map(_int, _input().split())
    values[p] += x
  calc_results(results, 0, 1)
  print(*[results[i] for i in range(1, n + 1)])
main()
### BUGGY CODE ###

s,k = input().split()
K = int(k)
if s[-1] == "1":
  s += "0"
n = len(s)
ls = []
cnt = 0
for i in range(n):
  if s[i] == "0":
    ls.append(cnt)
    cnt = 0
  else:
    cnt += 1
l = len(ls)
sm = sum(ls)
mod = 998244353
dp = [[[0 for i in range(sm+1)] for j in range(sm+1)] for k in range(l+1)]
dp[0][0][0] = 1
smprv = 0
for i in range(1,l+1):
  num = ls[i-1]
  for j in range(smprv+num,sm+1):
    if j == smprv+num:
      dp[i][j][0] = 1
    for k in range(1,j+1):
      for m in range(j+1):
        if num >= m:
          dp[i][j][k] += dp[i-1][j-m][k]
        else:
          dp[i][j][k] += dp[i-1][j-m][k-(m-num)]
        dp[i][j][k] %= mod
  smprv += num
ans = 0
for i in range(sm+1):
  if i <= K:
    ans += dp[-1][-1][i]
    ans %= mod
print(ans)

### FIXED CODE ###

s,k = input().split()
K = int(k)
if s[-1] == "1":
  s += "0"
n = len(s)
ls = []
cnt = 0
for i in range(n):
  if s[i] == "0":
    ls.append(cnt)
    cnt = 0
  else:
    cnt += 1
l = len(ls)
sm = sum(ls)
mod = 998244353
dp = [[[0 for i in range(sm+1)] for j in range(sm+1)] for k in range(l+1)]
dp[0][0][0] = 1
smprv = 0
for i in range(1,l+1):
  num = ls[i-1]
  for j in range(smprv+num,sm+1):
    if j == smprv+num:
      dp[i][j][0] = 1
    for k in range(1,j+1):
      x = 0
      for m in range(j+1):
        if num >= m:
          x += dp[i-1][j-m][k]
        else:
          x += dp[i-1][j-m][k-(m-num)]
      dp[i][j][k] = x%mod
  smprv += num
ans = 0
for i in range(sm+1):
  if i <= K:
    ans += dp[-1][-1][i]
    ans %= mod
print(ans)
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    l = len(bin(max(A))[2:])
    mask = int("1"*N, 2)
    cols = ["" for _ in range(l)]
    for i in range(N):
        A[i] = bin(A[i])[2:].zfill(l)
        for j in range(l):
            cols[j] += A[i][j]
    #print(A)
    #print(cols)
    for i in range(l):
        if cols[i][1:].count("1") % 2 == int(A[0][i]):
            continue
        else:
            cols[i] = bin(int(cols[i], 2) ^ mask)[2:].zfill(N)
    #print(cols)
    ans = ["" for _ in range(N)]
    for c in cols:
        for i in range(N):
            ans[i] += c[i]
    #print(ans)
    print(*(map(lambda x: int(x, 2), ans))) 
    


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    B = A[0]
    for i in range(1, N):
        B = B^A[i]
    ans = []
    for i in range(N):
        ans.append(B^A[i])
    print(*ans)

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

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = np.zeros((N+1, S+1), np.int32)
dp[0][0] = 1
#dp = np.array([[0] * (S+1) for _ in range(N+1)])  # dp[i][j]はi個選んだ合計jの個数
for a in A:
    for i in range(N-1, -1, -1):
        dp[i+1][a:] += dp[i][:-a]

dpS = dp[:, S]
answer = 0
for i, x in enumerate(dpS):
    answer += pow(2, (N-i), MOD) * x
    answer %= MOD
print(answer)


### FIXED CODE ###

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = np.zeros(S+1, np.int64)
dp[0] = 1
for a in A:
    prev = dp.copy()
    dp[a:] += dp[:-a]
    dp += prev
    dp %= MOD

answer = dp[S]
print(answer%MOD)
### BUGGY CODE ###

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

n, d, a = map(int, input().split())

x = []
h = {} # x:h
for _ in range(n):
    i, j = map(int, input().split())
    x.append(i)
    h[i] = j
x.sort()

ans = 0
attack = [0 for _ in range(n)]
for i in range(n):
    attack[i] += attack[i-1]
    if attack[i] >= h[x[i]]:
        continue

    if (h[x[i]] - attack[i]) % a == 0:
        k = (h[x[i]] - attack[i]) // a
    else:
        k = (h[x[i]] - attack[i]) // a + 1
    attack[i] += a * k
    ans += k

    for j in range(i+1, n):
        if x[j] > x[i] + 2*d:
            attack[j] -= a * k
            break

print(ans)

### FIXED CODE ###

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

n, d, a = map(int, input().split())

x = []
h = {} # x:h
for _ in range(n):
    i, j = map(int, input().split())
    x.append(i)
    h[i] = j
x.sort()
x.append(x[-1] + 2*d + 1)

# attackで累積和を用いる
ans = 0
attack = [0 for _ in range(n+1)]
for i in range(n):
    attack[i] += attack[i-1]
    if attack[i] >= h[x[i]]:
        continue

    if (h[x[i]] - attack[i]) % a == 0:
        j = (h[x[i]] - attack[i]) // a
    else:
        j = (h[x[i]] - attack[i]) // a + 1
    attack[i] += a * j
    ans += j

    # 二分探索で、x[y] > x[i] + 2*d、を満たす最小のyを求める
    # start <= y <= stop
    start = i + 1
    stop = n
    k = stop - start + 1
    while k > 1:
        if x[start + k//2 - 1] <= x[i] + 2*d:
            start += k//2
        else:
            stop = start + k//2 - 1
        k = stop - start + 1
    attack[start] -= a * j

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

from collections import deque
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans = [[] for i in range(n)],[[] for i in range(n)],n
for i,j in b:
	x[i].append(j)
	x[j].append(i)
def f(s):
	for i in range(n):
		q,v = deque(),[1]*n
		v[i] = 0
		for j in x[i]:
			q.append((j,1,j))
			d[i].append(j)
			v[j] = 0
		while q:
			p = q.pop()
			if p[1]<s:
				for j in x[p[0]]:
					if v[j]:
						q.append((j,p[1]+1,p[2]))
						d[i].append(p[2])
						v[j] = 0
if k==1: ans = n-2
elif k%2:
	f((k-1)//2)
	for i in range(n-1):
		d1,d2 = d[b[i][0]],d[b[i][1]]
		ans = min(ans,n-len(d1)-len(d2)+d1.count(b[i][1])+d2.count(b[i][0])-2)
else:
	f(k//2)
	for i in range(n): ans = min(ans,n-len(d[i])-1)
print(ans)

### FIXED CODE ###

from collections import deque
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans,c = [[] for i in range(n)],[[] for i in range(n)],n,0
for i,j in b:
	x[i].append(j)
	x[j].append(i)
def f(s):
	for i in range(n):
		q,v = deque(),[1]*n
		v[i] = 0
		for j in x[i]:
			q.append((j,1,j))
			d[i].append(j)
			v[j] = 0
		while q:
			p = q.pop()
			if p[1]<s:
				for j in x[p[0]]:
					if v[j]:
						q.append((j,p[1]+1,p[2]))
						d[i].append(p[2])
						v[j] = 0
if k>n//2:
	for i in x: c = max(len(i),c)
if n-c+1<=k: ans = 0
elif k==1: ans = n-2
else:
	f(k//2)
	if k%2:
		for i,j in b: ans = min(ans,n-len(d[i])-len(d[j])+d[i].count(j)+d[j].count(i)-2)
	else:
		for i in range(n): ans = min(ans,n-len(d[i])-1)
print(ans)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
*A, = map(int, input().split())
INF = 10**20
dp = [[defaultdict(lambda :-INF) for _ in range(N+1)] for _ in range(2)]
dp[0][0][0] = 0

for i in range(1, N+1):
    for j in range(i+1):
        dp[1][i][j] = max(dp[1][i][j], dp[0][i-1][j-1]+A[i-1])
        dp[0][i][j] = max(dp[1][i-1][j], dp[0][i-1][j])

ans = max(dp[1][N][N//2], dp[0][N][N//2])
print(ans)


### FIXED CODE ###

from collections import defaultdict

N = int(input())
*A, = map(int, input().split())
INF = 10**20
dp = [[defaultdict(lambda :-INF) for _ in range(N+1)] for _ in range(2)]
dp[0][0][0] = 0

for i in range(1, N+1):
    for j in range(i//2-1, i//2+2):
        dp[1][i][j] = max(dp[1][i][j], dp[0][i-1][j-1]+A[i-1])
        dp[0][i][j] = max(dp[1][i-1][j], dp[0][i-1][j])

ans = max(dp[1][N][N//2], dp[0][N][N//2])
print(ans)
### BUGGY CODE ###

s=input()

s = list(s)

ans = 0

for i in range(len(s)-1):
    if s[i] != 'A': continue
    for j in range(i+1,len(s)):
        if s[j] == 'Z':
            ans = max(ans, j-i+1)
print(ans)

### FIXED CODE ###

s=input()

s = list(s)

memo1=10000000000000000000000

ans = 0

for i in range(len(s)):
    if s[i] == 'A':
        memo1=min(memo1, i)
    if s[i] == 'Z':
        memo2=i
print(memo2-memo1+1)
### BUGGY CODE ###

import numpy as np

def fn(N, K, A):
    for _ in range(K):
        B = np.zeros(N, dtype=np.int64)
        for i in range(N):
            l = max(0, i - A[i])
            r = min(N - 1, i + A[i])

            B[l] += 1
            if (r + 1 < N):
                B[r + 1] -= 1

        A = np.cumsum(B)
        if (np.all(A == N)):
            return A
    return A

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A, dtype=np.int64)

B = fn(N, K, A)
print(" ".join(B.astype(str)))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

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

@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

H, N = map(int, input().split())
inf = 1 << 32
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
    a,b = map(int, input().split())
    for j in range(H+1):
        dp[min(H,j + a)] = min(dp[min(H,j + a)], dp[j] + b)
print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split())
inf = 1 << 32
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
    a,b = map(int, input().split())
    for j in range(H+1):
        dp[min(H,j + a)] = min(dp[min(H,j + a)], dp[j] + b)
print(dp[H])