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

import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    road_r = defaultdict(set)
    rail_r = defaultdict(set)
    for i in range(N):
        road_r[road.find(i)].add(i)
        rail_r[rail.find(i)].add(i)

    memo = [[-1 for _ in range(N)] for _ in range(N)]
    ans = [0 for _ in range(N)]
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)

        if memo[n][m] != -1:
            ans[i] = memo[n][m]
        else:
            a = len(road_r[n] & rail_r[m])
            memo[n][m] = a
            ans[i] = a

    return print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    d = defaultdict(lambda: 0)
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        d[(n, m)] += 1

    ans = []
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        ans.append(d[(n, m)])

    return print(*ans)


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

N = int(input())
A = []
for i in range(N):
    A.append(input())

List = []
for i in range(N):
    temp = {}
    for j in range(10):
        if A[i][j] in temp:
            temp[A[i][j]] += 1
        else:
            temp[A[i][j]] = 1
    List.append(temp)
    
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if List[i] == List[j]:
            ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]

L = ["0"]*N
for i in range(N):
    temp = ["0"]*10
    for j in range(10):
        temp[j] = S[i][j]
    temp.sort()
    L[i] = temp
        
L.sort()
ans = 0
cnt = 1
temp = L[0]
for i in range(1, N):
    if temp == L[i]:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
        temp = L[i]
        
ans += cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
factors = []
i = 2
while N > 1:
  while N % i == 0:
    factors.append(i)
    N //= i
  i += 1

ans = 0
for count in Counter(factors).values():
  i = 1
  while count >= i:
    count -= i
    i += 1
    ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
factors = []
i = 2
while N > 1:
  if N < i * i:
    factors.append(N)
    break
  while N % i == 0:
    factors.append(i)
    N //= i
  i += 1

ans = 0
for count in Counter(factors).values():
  i = 1
  while count >= i:
    count -= i
    i += 1
    ans += 1
print(ans)
### BUGGY CODE ###

def totalcost_recur(i,cost,N,lookup):
  if i>=N:
    return 0
  if i in lookup:
      return lookup[i]
  option1 = abs(cost[i]-cost[i+1]) + totalcost_recur(i+1,cost,N,lookup)
  ans = option1
  if i+2<=N:
    option2 = abs(cost[i]-cost[i+2]) + totalcost_recur(i+2,cost,N,lookup)
    ans = min(option2,ans)
  lookup[i] = ans
  return ans



def totalcost_dp(cost,N,k):
    dp = [float('inf')]*(N+1)
    dp[1] = 0
    
    
    for i in range(1,N+1):
        
        for j in range(i+1,k+i+1):
            if j < N+1:
                dp[j] = min(dp[j],dp[i]+abs(cost[i]-cost[j]))
                
            
        
        

    return dp[N]


n ,k= map(int,input().split())
cost = list(map(int,input().split()))
cost = [0]+cost
lookup = {}

print(totalcost_dp(cost,n,k))

### FIXED CODE ###


def totalcost_dp(cost,N,k):
    dp = [float('inf')]*(N+1)
    dp[1] = 0
    
    
    for i in range(1,N+1):
        
        for j in range(i+1,k+i+1):
            if j < N+1:
                dp[j] = min(dp[j],dp[i]+abs(cost[i]-cost[j]))
                
    return dp[N]


n ,k= map(int,input().split())
cost = list(map(int,input().split()))
cost = [0]+cost
print(totalcost_dp(cost,n,k))
### BUGGY CODE ###

n = int(input())
aiList = [int(input()) for i in range(n)]
count = 0
visited = [1]
now = 1
while True:
    count += 1
    nextNum = aiList[now - 1]
    if nextNum == 2:
        break
    if nextNum in visited:
        count = -1
        break
    visited.append(nextNum)
    now = nextNum
print(count)

### FIXED CODE ###

n = int(input())
aiList = [int(input()) for i in range(n)]
count = 0
now = 1
while True:
    count += 1
    if count >= n:
        count = -1
        break
    nextNum = aiList[now - 1]
    if nextNum == 2:
        break
    now = nextNum
print(count)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
q = deque()
keys = [0] * n
dic = {i: [] for i in range(n)}
for _ in range(m):
    a, b = map(int, input().split())
    dic[a - 1].append(b - 1)
    dic[b - 1].append(a - 1)

for i in dic[0]:
    q.append(i)
    keys[i] = 1
while len(q) > 0:
    next = q.popleft()
    for i in dic[next]:
        if i == 0:
            continue
        if keys[i]:
            continue
        if i not in q:
            q.append(i)
            keys[i] = next + 1
print('Yes')
print(*keys[1:], sep='\n')

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
q = deque()
t = {i: set() for i in range(1, n + 1)}
v = [-1] * n

for _ in range(m):
    a, b = map(int, input().split())
    t[a].add(b)
    t[b].add(a)
q.append(1)
v[0] = 1
while q:
    next = q.popleft()
    for i in t[next]:
        if v[i - 1] == -1:
            q.append(i)
            v[i - 1] = next
print('Yes')
print(*v[1:], sep='\n')
### BUGGY CODE ###

n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[i] for i in range(n)]
rail=[[i] for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].extend(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].extend(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[0]*n
for i in range(n):
    if ans[i]!=0:
        continue
    sumset=set(road[i])&set(rail[i])
    for j in sumset:
        ans[j]=str(len(sumset))
print(" ".join(ans))

### FIXED CODE ###

n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[{i} for i in range(n)]
rail=[{i} for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].add(q)
    road[q].add(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].add(s)
    rail[s].add(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].update(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].update(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[0]*n
for i in range(n):
    if ans[i]!=0:
        continue
    sumset=road[i]&rail[i]
    for j in sumset:
        ans[j]=str(len(sumset))
print(" ".join(ans))
### BUGGY CODE ###

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

LR = [[0 for i in range(2)] for j in range(M)]
pq = [[0 for i in range(2)] for j in range(Q)]

for i in range(M):
    LR[i] = list(map(int, input().split()))

for i in range(Q):
    pq[i] = list(map(int, input().split()))

x = [[0 for i in range(N)] for j in range(N)]

# print(LR[0][0])

for i in range(M):
    x[LR[i][1] - 1][LR[i][0] - 1] = x[LR[i][1] - 1][LR[i][0] - 1] + 1

xacu = [[0 for i in range(N)] for j in range(N)]

for i in range(N):
    for j in range(N):
        if j == 0:
            xacu[i][j] = x[i][j]
        else:
            xacu[i][j] = xacu[i][j - 1] + x[i][j]

# print(xacu)

for i in range(Q):
    count = 0
    p = pq[i][0]
    for j in range(pq[i][1]):
        if p == 1:
            count = count + xacu[j][N - 1]
        else:
            count = count + xacu[j][N - 1] - xacu[j][p - 2]

    print(count)


### FIXED CODE ###

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

x = [[0 for i in range(N + 1)] for j in range(N + 1)]

for i in range(M):
    l, r = map(int, input().split())
    x[l][r] += 1

for i in range(1, N + 1):
    for j in range(1, N + 1):
        x[i][j] += x[i - 1][j] + x[i][j - 1] - x[i - 1][j - 1]

for i in range(Q):
    p, q = map(int, input().split())

    ans = x[N][q] - x[p - 1][q]
    print(ans)
### BUGGY CODE ###

from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
modulo = 998244353

dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    for j in range(s + 1):
        dp[i + 1][j] = dp[i][j] * 2
        if j - a[i] >= 0:
            dp[i + 1][j] += dp[i][j - a[i]]

        if dp[i + 1][j] > modulo:
            dp[i + 1][j] -= modulo
sol = 3 ** n - 3 * sum(dp[-1][int((s + 1) / 2) :])


if s % 2 == 0:
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(n):
        for j in range(s + 1):
            dp[i + 1][j] = dp[i][j]
            if j - a[i] >= 0:
                dp[i + 1][j] += dp[i][j - a[i]]

            if dp[i + 1][j] > modulo:
                dp[i + 1][j] -= modulo

    sol += 3 * dp[-1][s // 2]
sol %= modulo

print(sol)



### FIXED CODE ###

import numpy as np
from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = np.zeros(s + 1, dtype=np.int)
dp[0] = 1
for ai in a:
    dp[ai:] = 2 * dp[ai:] + dp[:-ai]
    dp[:ai] = 2 * dp[:ai]
    dp %= modulo
sol = 3 ** n % modulo
sol -= 3 * dp[ceil(s / 2) :].sum()


if s % 2 == 0:
    dp = np.zeros(s + 1, dtype=np.int)
    dp[0] = 1
    for ai in a:
        dp[ai:] = dp[ai:] + dp[:-ai]
        dp %= modulo

    sol += 3 * dp[s // 2]

sol %= modulo

print(sol)
### BUGGY CODE ###

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

x-=1
y-=1
ans=[0 for i in range(n)]
for i in range(n):
    d=[100000 for i in range(n)]
    d[i]=0
    q=[]
    q.append(i)
    while q:
        p=q.pop()
        if(p-1>=0 and d[p]+1<d[p-1]):
            q.append(p-1)
            d[p-1]=d[p]+1
        if(p+1<n and d[p]+1<d[p+1]):
            q.append(p+1)
            d[p+1]=d[p]+1

        if(p==x and d[x]+1<d[y]):
            q.append(y)
            d[y]=d[x]+1
        if(p==y and d[y]+1<d[x]):
            q.append(x)
            d[x]=d[y]+1

    for j in range(n):ans[d[j]]+=1


for i in range(1,n):
    print(ans[i]//2)

### FIXED CODE ###

n,x,y=map(int,input().split())
x-=1
y-=1
d=[10000 for i in range(n)]
ans=[0 for i in range(n)]
for i in range(n):
    for j in range(i,n):
        m=min(abs(i-j),abs(x-i)+abs(y-j)+1,abs(y-i)+abs(x-j)+1)
        ans[m]+=1

for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]

light = [[-1, -1] for _ in range(H*W)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        
        if light[W*i+j][0] == -1:
            tmp = 0
            tate = i
            while tate < H and S[tate][j] == '.':
                tmp += 1
                tate += 1
            for k in range(tmp):
                light[W*(i+k)+j][0] = tmp
        
        if light[W*i+j][1] == -1:
            tmp = 0
            yoko = j
            while yoko < W and S[i][yoko] == '.':
                tmp += 1
                yoko += 1
            for k in range(tmp):
                light[W*i+j+k][1] = tmp

ans = 0
for i in light:
    tmp = i[0]+i[1]-1
    if tmp > ans:
        ans = tmp

print(ans)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
up = np.zeros((H, W), dtype=int)
down = np.zeros((H, W), dtype=int)
left = np.zeros((H, W), dtype=int)
right = np.zeros((H, W), dtype=int)
 
for i in range(H):
    up[i] = (up[i-1] + 1) * S[i]
    down[-i-1] = (down[-i] + 1) * S[-i-1]

for i in range(W):
    left[:, i] = (left[:, i-1] + 1) * S[:, i]
    right[:, -i-1] = (right[:, -i] + 1) * S[:, -i-1]

print(np.max(up+down+left+right)-3)
### BUGGY CODE ###

X = int(input())
X_MOD = X % 100
X_DIV = X // 100
def bfs():
    
    from collections import deque
    queue = deque([(0, 0)])
    while queue:
        sum_x, cnt_x = queue.popleft()
        #print(sum_x, cnt_x)
        if sum_x == X_MOD:
            return 1
        if sum_x > X_MOD:
            continue
        if cnt_x == X_DIV:
            continue

        queue.append((sum_x + 1,cnt_x+1))
        queue.append((sum_x + 2,cnt_x+1))
        queue.append((sum_x + 3,cnt_x+1))
        queue.append((sum_x + 4,cnt_x+1))
        queue.append((sum_x + 5,cnt_x+1))
    return 0

ans = bfs()
print(ans)

### FIXED CODE ###

X = int(input())
X_MOD = X % 100
X_DIV = X // 100

import sys
sys.setrecursionlimit(2000)
def dfs(sum_x, cnt_x, num):
    if cnt_x > X_DIV:
        return False
    if sum_x == X_MOD:
        return True

    if num == 1:
        return dfs(sum_x+1, cnt_x+1, 1) or dfs(sum_x+1, cnt_x+2, 2) or dfs(sum_x+3, cnt_x+1, 3) or dfs(sum_x+4, cnt_x+1, 4) or dfs(sum_x+5, cnt_x+1, 5)
    if num == 2:
        return dfs(sum_x+1, cnt_x+2, 2) or dfs(sum_x+3, cnt_x+1, 3) or dfs(sum_x+4, cnt_x+1, 4) or dfs(sum_x+5, cnt_x+1, 5)
    if num == 3:
        return dfs(sum_x+3, cnt_x+1, 3) or dfs(sum_x+4, cnt_x+1, 4) or dfs(sum_x+5, cnt_x+1, 5)
    if num == 4:
        return dfs(sum_x+4, cnt_x+1, 4) or dfs(sum_x+5, cnt_x+1, 5)
    if num == 5:
        return dfs(sum_x+5, cnt_x+1, 5)
    

ans = int(dfs(0,0,1))
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    numlist = []
    for _ in range(n):
        numlist.append(int(input()))

    maxprofit = numlist[1] - numlist[0]
    for i in range(n-1):
        for j in range(i+1, n):
            if numlist[j] - numlist[i] > maxprofit:
                maxprofit = numlist[j] - numlist[i]
    print(maxprofit)


if __name__ == '__main__':
    main()



### FIXED CODE ###

n = int(input())
a0 = int(input())
a1 = int(input())
max_profit = a1 - a0
min_i = min(a1, a0)
for i in range(n-2):
    c=int(input())
    if c - min_i > max_profit:
        max_profit = c - min_i
    min_i = min(min_i, c)
print(max_profit)
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split(" ")]
mul=1
for a in A:
    mul*=a

if mul>10**18:
    print(-1)
else:
    print(mul)


### FIXED CODE ###

import sys
N=int(input())
A=[int(i) for i in input().split(" ")]
if 0 in A:
    print(0)
    sys.exit(0)
A=sorted(A,reverse=True)
mul=1
for a in A:
    mul*=a

    if mul>10**18:
        print(-1)
        sys.exit(0)

print(mul)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W,M=map(int,input().split())#slow,行数H、列数W、爆弾数M
hcnt=[0]*H#何行目に何個あるか
wcnt=[0]*W#何列目に何個あるか
bomb=[]

for i in range(M):
    bh,bw=map(int,input().split())
    hcnt[bh-1]+=1#行方向
    wcnt[bw-1]+=1#列方向
    bomb.append([bh-1,bw-1])
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax=max(set(hcnt))#2
wmax=max(set(wcnt))#1
hmaxindex=[i for i in range(H) if hcnt[i]==hmax]#[0]
wmaxindex=[i for i in range(W) if wcnt[i]==wmax]#[0,1,2]
#crosspoint has not bomb

for i in hmaxindex:
    for j in wmaxindex:
        if [i,j] not in bomb:
            print(hmax+wmax)
            sys.exit()
        else:
            continue
#all crosspoint has bomb
print(hmax+wmax-1)


### FIXED CODE ###


import sys
from collections import Counter

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1

crs = 0#hmax and wmax crosspoint
for (i, j) in bomb:
    if hcnt[i] == hmax and wcnt[j] == wmax:
        crs += 1
#all crosspoint has bomb
if crs == Counter(hcnt)[hmax] * Counter(wcnt)[wmax]:
    print(hmax + wmax - 1)
#more than one crosspoint has no bomb
else:
    print(hmax + wmax)
### BUGGY CODE ###

def clear_maze(sx, sy, gx, gy, maze):

    INF = 100000000

    distance = [[INF for i in range(W)] for j in range(H)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sy][sx] = 0

        while len(queue):
            x, y = queue.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < W and 0 <= ny and ny < H and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (nx, ny))
                    distance[ny][nx] = distance[y][x] + 1


        return distance[gy][gx]

    return bfs()

H,W = (int(x) for x in input().split())
maze = ['']*H
max_distance = 0
for i in range(H):
  maze[i] = list(input())
for sy in range(H):
  for sx in range(W):
    if maze[sy][sx] == '#':
      continue
    for gy in range(H):
      for gx in range(W):
        if (sx == gx and sy == gy) or maze[gy][gx] == '#':
          continue
        tmp_s = maze[sy][sx]
        tmp_g = maze[gy][gx]
        maze[sy][sx] = 'S'
        maze[gy][gx] = 'G'
        
        max_distance = max(max_distance,clear_maze(sx, sy, gx, gy, maze))
        maze[sy][sx] = tmp_s
        maze[gy][gx] = tmp_g
        
print(max_distance)
    

    

### FIXED CODE ###

from collections import deque
import math
import copy
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
def bfs(maze,h,w,sx,sy):
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=float('inf')

    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0 <= y+i < H and 0<=x+j<W:
                nexty,nextx=y+i,x+j
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    m = 0                   
    for l in maze:
      li = [i for i in l if i != '#' and i < 1000000]
      if len(li) > 0:
        m = max(m,max(li))
    return m
max_dist = -1  
for si in range(H):
  for sj in range(W):
    if maze[si][sj] == '#':
      continue
    copymaze = copy.deepcopy(maze)
    res = bfs(copymaze,H,W,sj,si)
    max_dist = max(max_dist,res)
print(max_dist)
### BUGGY CODE ###

N, M = map(int, input().split())
X = [ [] for j in range(N+1) ]
for i in range(M):
    a, b = map(int, input().split())
    X[a].append(b)
    X[b].append(a)

result = [0] * (N+1)
c = []
for x in X[1]:
    result[x] = 1
    c.append(x)

c_new = []
while 0 in result[2:]:
    for x in c:
        for y in X[x]:
            if result[y] == 0:
                result[y] = x
                c_new.append(y)
    c = c_new
    c_new = []

print('Yes')
for j in range(2, N+1):
    print(result[j])

### FIXED CODE ###

N, M = map(int, input().split())
X = [ [] for j in range(N+1) ]
for i in range(M):
    a, b = map(int, input().split())
    X[a].append(b)
    X[b].append(a)

result = [0] * (N+1)
c = []
flag = [0]*N
for x in X[1]:
    result[x] = 1
    c.append(x)
    flag[x-1]=True

c_new = []
while not all(flag):
    for x in c:
        for y in X[x]:
            if flag[y-1] == False:
                result[y] = x
                c_new.append(y)
                flag[y-1] = True
    c = c_new
    c_new = []

print('Yes')
for j in range(2, N+1):
    print(result[j])
### BUGGY CODE ###

import itertools
k,s=map(int,input().split())
x=(x for x in range(0,k+1))
y=(y for y in range(0,k+1))
z=(z for z in range(0,k+1))
data=list(itertools.product(x,y,z))
ans=[sum(i) for i in (data)]
print(ans.count(s))


### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k and x+y+z == s:
            ans += 1
print(ans)
### BUGGY CODE ###

from fractions import Fraction
from math import ceil
import heapq
n,k, *aa = map(Fraction, open(0).read().split())
k = int(k)

hq = [(-a,-1,-a) for a in aa]
heapq.heapify(hq)

for _ in range(k):
    v,cnt,orig = heapq.heappop(hq)
    cnt *= -1
    cnt += 1
    v = orig / cnt
    cnt *= -1
    heapq.heappush(hq, (v,cnt,orig))

print(max([ceil(-a) for a,b,c in hq]))

### FIXED CODE ###

from math import ceil

n,k, *aa = map(int, open(0).read().split())

left = 0
right = 10**9

while right - left > 1:
    mid = (left + right) // 2
    summ = sum(0--a//mid-1 for a in aa)
    if summ <= k:
        right = mid
    else:
        left = mid

print(right)
### BUGGY CODE ###

import sys

s=list(input())
q=int(input())

re=0
for i in range(1,q+1):
    q_i=sys.stdin.readline().rstrip().split()
    if q_i[0]=="1":
        re+=1
    else:
        if q_i[1]=="1" and re%2==0:
            s=[q_i[2]]+s
        elif q_i[1]=="2" and re%2==1:
            s=[q_i[2]]+s
        else:
            s=s+[q_i[2]]

if re%2==1:
    s=s[::-1]

s="".join(s)
print(s)

### FIXED CODE ###

from collections import deque

s=list(input())
s=deque(s)
q=int(input())

re=False
for i in range(1,q+1):
    q_i=input().split()
    if q_i[0]=="1":
        re= not re
    else:
        if q_i[1]=="1" and re==False:
            s.appendleft(q_i[2])
        elif q_i[1]=="2" and re==True:
            s.appendleft(q_i[2])
        else:
            s.append(q_i[2])

s=list(s)

if re==True:
    s=s[::-1]

s="".join(s)
print(s)