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

def main():
    from sys import stdin
    from collections import deque
    import sys
    H, W = map(int, stdin.readline().split())
    ch, cw = map(int, stdin.readline().split())
    dh, dw = map(int, stdin.readline().split())
    ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
    S = [input() for _ in range(H)]
    d = [[0]*W for _ in range(H)]

    que = deque([[cw, ch]])
    count = 0
    while que:
        while que:
            x, y = que.popleft()
            if x == dw and y == dh:
                print(count)
                sys.exit()
                
            d[y][x] = -1
            for i in range(-2, 3):
                for j in range(-2, 3):
                    nnx, nny = x+i, y+j
                    if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                        d[nny][nnx] = 1
        
            for dx, dy in [1, 0], [0, 1], [-1, 0], [0, -1]:
                nx, ny = x+dx, y+dy
                if 0<=nx<W and 0<=ny<H and S[ny][nx]!='#' and d[ny][nx]!=-1:
                    if nx == dw and ny == dh:
                        print(count)
                        sys.exit()
                
                    d[ny][nx] = -1
                    for i in range(-2, 3):
                        for j in range(-2, 3):
                            nnx, nny = nx+i, ny+j
                            if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                                d[nny][nnx] = 1
                    que.append([nx, ny])
                
        for i in range(W):
            for j in range(H):
                if d[j][i] == 1:
                    d[j][i] == -1
                    que.append([i, j])
        count += 1
    print(-1)

main()

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
s = [input() for _ in range(H)]

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

que = deque([[cw, ch, 0]])
while que:
    x, y, cost = que.popleft()
    if d[y][x]==-1 or d[y][x]>cost:
        d[y][x] = cost
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x+dx, y+dy
                if 0<=nx<W and 0<=ny<H and s[ny][nx]!='#':
                    if abs(dx)+abs(dy) == 1:
                        que.appendleft([nx, ny, cost])
                    else:
                        que.append([nx, ny, cost+1])  
print(d[dh][dw])
### BUGGY CODE ###

from collections import deque
def calcXor(nums):
  x=0
  for n in nums:
    x=x^n
  return x

N=int(input())
A=list(map(int,input().split()))
ans=deque()
for i in range(N):
  #print(A[0:i])
  x=calcXor(A[0:i])
  #print(A[i+1:N])
  y=calcXor(A[i+1:N])
  ans.append(x^y)
print(" ".join(map(str,ans)))



### FIXED CODE ###

from collections import deque
def calcXor(nums):
  x=0
  for n in nums:
    x=x^n
  return x

N=int(input())
A=list(map(int,input().split()))
A_xor=calcXor(A)

ans=deque()
for a in A:
  ans.append(A_xor^a) 

#for i in range(N):  
  #print(A[0:i])
  #x=calcXor(A[0:i])
  #print(A[i+1:N])
  #y=calcXor(A[i+1:N])
  #ans.append(x^y)
print(" ".join(map(str,ans)))
### BUGGY CODE ###

import numpy as np

N = int(input())
A = list([int(x) for x in input().split()])

left = []
right = []

for key, v in enumerate(A):
    s = [0] * N
    s[key] = 1

    if key+1 == N:
        s[0] = 1
    else:
        s[key+1] = 1
    left.append(s)

    right.append([v])

a = np.matrix(left)
b = np.matrix(right)

result = np.linalg.solve(a, b).flatten().tolist()[0]
print(' '.join([str(int(x) * 2) for x in result]))


### FIXED CODE ###

N = int(input())
A = list([int(x) for x in input().split()])

result = [0] * N
x = 0
for key, i in enumerate(A):
    if key % 2 == 0:
        x += i
    else:
        x -= i

result[0] = x

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

print(' '.join([str(x) for x in result]))
### BUGGY CODE ###

import statistics
N = int(input())
A = list(map(int,input().rstrip().split()))

i = 0
kari =[]
for j in A:
    i +=1
    B = j-i
    kari.append(B)

sum = 0
for i in kari:
    sum+=abs(i-statistics.median(kari))
print(int(sum))

### FIXED CODE ###

import math
import statistics
N = int(input())

A = input().rstrip().split()
#print(A)
i = 0
kari =[]
for j in A:
    i +=1
    B = int(j)-i
    kari.append(B)
#print(kari)
b = statistics.median(kari)

sum = 0
for i in kari:
    sum+=abs(i-b)
print(int(sum))
### BUGGY CODE ###

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

for i in range(n):
  print(a.count(i+1))

### FIXED CODE ###

import collections

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


ac = collections.Counter(a)

for i in range(n):
  print(ac[i+1])
### BUGGY CODE ###

A,B,Q = map(int, input().split())
S = [int(input()) for i in range(A)]
T = [int(input()) for i in range(B)]
X = [int(input()) for x in range(Q)]

L = []
for i in range(A):
    L.append([S[i], "s"])
for i in range(B):
    L.append([T[i], "t"])
for i in range(Q):
    L.append([X[i], "x", i])
    
L.sort()
ans = []
for i in range(len(L)):
    if L[i][1] == "x":
        c = i+1
        jud = []
        temp_s = []
        temp_t = []
        cnt = 0
        while c < len(L) and len(jud) < 2:
            if L[c][1] == "s" and "s" not in jud:
                jud.append("s")
                temp_s.append(L[c][0]-L[i][0])
            if L[c][1] == "t" and "t" not in jud:
                jud.append("t")
                temp_t.append(L[c][0]-L[i][0])
            c += 1
        if len(temp_s) == 0:
            temp_s.append(10**11+1)
        if len(temp_t) == 0:
            temp_t.append(10**11+1)
        c = i-1
        jud = []
        while c >= 0 and len(jud) < 2:
            if L[c][1] == "s" and "s" not in jud:
                jud.append("s")
                temp_s.append(L[c][0]-L[i][0])
            if L[c][1] == "t" and "t" not in jud:
                jud.append("t")
                temp_t.append(L[c][0]-L[i][0])
            c -= 1
        if len(temp_s) == 1:
            temp_s.append(-10**11-1)
        if len(temp_t) == 1:
            temp_t.append(-10**11-1)
        temp = []
        temp.append(max(temp_s[0], temp_t[0]))
        temp.append(max(-temp_s[1], -temp_t[1]))
        temp.append(min(2*temp_s[0]-temp_t[1], temp_s[0]-2*temp_t[1]))
        temp.append(min(2*temp_t[0]-temp_s[1], temp_t[0]-2*temp_s[1]))
        ans.append([L[i][2], min(temp)])
        
        
ans.sort()
for i in range(Q):
    print(ans[i][1])

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]

for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

# coding: utf-8
import sys
import math
import fractions
input = sys.stdin.readline


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


a, b = map(int, input().split())
x = fractions.gcd(a, b)
check_list = [1]
i = 2
while (1):
    flag = False
    if i > x:
        break
    while(x % i == 0):
        x /= i
        flag = True

    if flag == True:
        check_list.append(i)
    i += 1

# print(check_list)

ans = 1
for check in check_list:
    if is_prime(check):
        ans += 1

print(ans)


### FIXED CODE ###

# coding: utf-8
import sys
import math
import fractions
input = sys.stdin.readline


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


a, b = map(int, input().split())
x = fractions.gcd(a, b)
check_list = []
i = 2
"""
while (1):
    flag = False
    if i > x:
        break
    while(x % i == 0):
        x /= i
        flag = True

    if flag == True:
        check_list.append(i)
    i += 1
"""
while x % 2 == 0:
    check_list.append(2)
    x //= 2
i = 3
while i * i <= x:
    if x % i == 0:
        check_list.append(i)
        x //= i
    else:
        i += 2
if x != 1:
    check_list.append(x)

print(len(set(check_list))+1)

# print(check_list)
"""
ans = 1
for check in check_list:
    if is_prime(check):
        ans += 1

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

import sys
input = sys.stdin.readline

s1=input()
s2=input()
n=len(s1)
m=len(s2)
# import numpy as np
dp=[["" for i in range(m+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+s1[i-1]
        else:
            a=dp[i-1][j]
            b=dp[i][j-1]
            if len(a)>len(b):
                dp[i][j]=a
            else:
                dp[i][j]=b
# print(np.array(dp))
print(dp[-1][-1])

### FIXED CODE ###

s1=input()
s2=input()
n=len(s1)
m=len(s2)
# import numpy as np
dp=[[0 for i in range(m+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# print(np.array(dp))
ans=""
# print(dp[-1][-1])
i=n
j=m
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=s1[i-1]+ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

L=input()
N=len(L)

table=[1]
for i in range(1,100001):
    table.append(3*table[i-1])


bit=[]
for i in range(0,N):
    if L[N-1-i]=='1':
        bit.append(i+1)

dp=[0 for i in range(0,100001)]

m=bit[0]
if m!=1:
    dp[m]=(2+3**(m-1))%(10**9+7)
else:
    dp[m]=3
for i in range(1,len(bit)):
    s=bit[i]
    t=bit[i-1]
    dp[s]=(2*dp[t]+table[s-1])
print(dp[N]%(10**9+7))

### FIXED CODE ###

import time

def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K*x)%(10**9+7)
        x = (x*x)%(10**9+7)
        n //= 2

    return (K*x)%(10**9+7)

L=input()
N=len(L)


bit=[]
for i in range(0,N):
    if L[N-1-i]=='1':
        bit.append(i+1)

dp=[0 for i in range(0,100001)]

m=bit[0]
if m!=1:
    dp[m]=(2+3**(m-1))%(10**9+7)
else:
    dp[m]=3
time0=time.time()
for i in range(1,len(bit)):
    s=bit[i]
    t=bit[i-1]
    dp[s]=(2*dp[t]+pow_k(3,s-1))
time1=time.time()
print(dp[N]%(10**9+7))
### BUGGY CODE ###

import sys
readline=sys.stdin.readline

S = int(readline())

# 最も多い箱の数は、N = S // 3個
# Nから1個の箱i個に対して、残った数値（S - 3 * i）を分ける場合の数を足し合わせる

N = S // 3

DIV = 10 ** 9 + 7
n = (10 ** 6) * 2
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

def nCr(n, r, DIV):
  if (r < 0 or r > n):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % DIV

ans = 0
for i in range(N, 0, -1):
  rest = S - 3 * i
  if rest <= 0:
    ans += 1
    continue
  # rest個をi個の箱に分ける
  # rest + i - 1 C min(rest, i - 1)
  ans += nCr(rest + i - 1, rest, DIV)
  ans %= DIV
  
print(ans)


### FIXED CODE ###

import sys
readline=sys.stdin.readline

S = int(readline())

# 最も多い箱の数は、N = S // 3個
# Nから1個の箱i個に対して、残った数値（S - 3 * i）を分ける場合の数を足し合わせる

N = S // 3

DIV = 10 ** 9 + 7
n = (10 ** 6) * 2
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

def nCr(n, r, DIV):
  if (r < 0 or r > n):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % DIV

ans = 0
for i in range(N, 0, -1):
  rest = S - 3 * i
  if rest <= 0:
    ans += 1
    continue
  # rest個をi個の箱に分ける
  # rest + i - 1 C min(rest, i - 1)
  ans += nCr(rest + i - 1, rest, DIV)
  ans %= DIV
  
print(ans)
### BUGGY CODE ###


import sys
input = sys.stdin.readline

def update(index, value, bit):
  #print('update', index, value)
  while index < len(bit):
    #print('update', index)
    bit[index] += value
    index += index & -index
  #print('done')
    
def cumsum(index, bit):
  ans = 0
  while index > 0:
    #print('cumsum', index)
    ans += bit[index]
    index -= index & -index
  #print('done', ans)
  return ans

def main():
  N, q = [int(x) for x in input().split()]
  C = [int(x)-1 for x in input().split()]
  Q = []
  for _ in range(q):
    Q.append(tuple(int(x)-1 for x in input().split()[::-1]))
  I = sorted(range(q), key=Q.__getitem__)
  #print(I, Q)
  leftmost = [-1] * N
  bit = [0] * (N+1)
  prev = -1
  ans = [0] * q
  for i in I:
    r, l = Q[i]
    #print(i, r, l)
    to_update = {}
    for x in range(prev+1, r+1):
      to_update[C[x]] = x
    for c, x in to_update.items():
      if leftmost[c] >= 0:
        update(leftmost[c] + 1, -1, bit)
      leftmost[c] = x
      update(x + 1, 1, bit)
    prev = r
    #print(i, r, l)
    #print(C)
    #print([cumsum(i, bit) for i in range(1, N+1)])
    ans[i] = cumsum(r + 1, bit) - cumsum(l, bit)
  for a in ans:
    print(a)
  

main()

### FIXED CODE ###


import sys
input = sys.stdin.readline

def update(index, value, bit):
  #print('update', index, value)
  while index < len(bit):
    #print('update', index)
    bit[index] += value
    index += index & -index
  #print('done')
    
    
def cumsum(index, bit):
  ans = 0
  while index > 0:
    #print('cumsum', index)
    ans += bit[index]
    index -= index & -index
  #print('done', ans)
  return ans
  

def main():
  N, q = [int(x) for x in input().split()]
  C = [int(x)-1 for x in input().split()]
  Q = []
  for i in range(q):
    l, r =  [int(x)-1 for x in input().split()]
    Q.append((i, l, r))
  Q.sort(key=lambda x: x[2])
  leftmost = [-1] * N
  bit = [0] * (N+1)
  prev = -1
  ans = [0] * q
  for i, l, r in Q:
    #print(i, r, l)
    to_update = {}
    for x in range(prev+1, r+1):
      to_update[C[x]] = x
    for c, x in to_update.items():
      if leftmost[c] >= 0:
        update(leftmost[c] + 1, -1, bit)
      leftmost[c] = x
      update(x + 1, 1, bit)
    prev = r
    #print(i, r, l)
    #print(C)
    #print([cumsum(i, bit) for i in range(1, N+1)])
    ans[i] = cumsum(r + 1, bit) - cumsum(l, bit)
    
  for a in ans:
    print(a)
  

main()
### BUGGY CODE ###

mod=10**9+7
n,k=map(int,input().split())
l=sorted(map(int,input().split()))
ll=list(map(lambda x:-1*x,l[::-1]))
ans=0
b,s=1,1
for i in range(k,n):
  s*=i
  b*=(i-k+1)
ml=s//b
ans-=ml*(l[0]+ll[0])
ans%=mod
for i in range(1,n-k+1):
  ml=ml*(n-i-k+1)//(n-i)
  ans-=ml*(l[i]+ll[i])%mod


print(ans%mod)


### FIXED CODE ###

n,k=map(int,input().split())
l=sorted(list(map(int,input().split())))
mod=10**9+7
fact=[1]*(n+1)
inv=[1]*(n+1)
for i in range(2,n+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
for i in range(n):
    if i>=k-1:
        ans+=l[i]*fact[i]*inv[k-1]*inv[i-k+1]%mod
    if n-i-1>=k-1:
        ans-=l[i]*fact[n-i-1]*inv[k-1]*inv[n-i-1-k+1]%mod
    ans%=mod
print(ans)
### BUGGY CODE ###

import sys
 
sys.setrecursionlimit(10000)

N,K,L = map(int, input().split())

#print(N,K,L,D,T)

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def execOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.union(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

execOne(K, uf_D)
execOne(L, uf_T)

res = [0] * N
for i in range(N):
    for j in range(N):
        if (uf_D.same_check(i,j) and uf_T.same_check(i,j)):
            res[i] += 1
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

### FIXED CODE ###

import sys
 
sys.setrecursionlimit(10000)

N,K,L = map(int, input().split())

#print(N,K,L,D,T)

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def execOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.union(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

execOne(K, uf_D)
execOne(L, uf_T)


pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))
### BUGGY CODE ###

K = int(input())
N = len(input())

mod = 10 ** 9 + 7
comb_i = 26 ** K
ans = comb_i
for i in range(1, K + 1):
  comb_i *= (N + i - 1) * 25
  comb_i //= i * 26
  ans += comb_i
  
print(ans % mod)

### FIXED CODE ###

K = int(input())
N = len(input())

mod = 10 ** 9 + 7
div = pow(26, -1, mod)
comb_i = pow(26, K, mod)
ans = comb_i
for i in range(1, K + 1):
  comb_i = (comb_i * (N - 1 + i) * pow(i, -1, mod)) % mod
  comb_i = (comb_i * 25 * div) % mod
  ans = (ans + comb_i) % mod
  
print(ans)
### BUGGY CODE ###

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int, input().split())
uf=UnionFind(n)
for _ in range(m):
    a,b=map(int, input().split())
    uf.union(a-1, b-1)
cnt=0
for l in list(uf.all_group_members().values()):
    cnt=max(cnt, len(l))

print(cnt)

### FIXED CODE ###

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int, input().split())
uf=UnionFind(n)
for _ in range(m):
    a,b=map(int, input().split())
    uf.union(a-1, b-1)
cnt=0
for i in range(n):
    cnt=max(cnt, uf.size(i))
print(cnt)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
ABs = [0] * N

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

ABs = sorted(ABs, reverse=True, key=lambda x: x[1])

rewards = [0] * (M + 1)

count = 0
for AB in ABs:
    day, reward = AB
    if day <= M:
        if rewards[day] == 0:
            rewards[day] = reward
            count += 1
        else:
            for i in range(day, M + 1):
                if rewards[i] == 0:
                    rewards[i] = reward
                    count += 1
                    break
    if count == M:
        break

result = sum(rewards)
print(result)

### FIXED CODE ###

N, M = list(map(int, input().split()))
ABs = [0] * N
day_dic = {}

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

ABs = sorted(ABs, reverse=True, key=lambda x: x[1])

rewards = [0] * (M + 1)

count = 0
for AB in ABs:
    day, reward = AB
    if day <= M:
        if rewards[day] == 0:
            rewards[day] = reward
            day_dic[day] = day
            count += 1
        else:
            esti = day_dic.get(day)
            if esti is None:
                esti = day
            for i in range(esti, M + 1):
                if rewards[i] == 0:
                    rewards[i] = reward
                    day_dic[day] = i
                    count += 1
                    break
    if count == M:
        break

result = sum(rewards)
print(result)
### BUGGY CODE ###

from collections import defaultdict

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

max_A = max(A)
j = 0
while max_A >> j > 0:
    j += 1
max_j = j

c = defaultdict(int)
ans = 0
MOD = 10 ** 9 + 7
for i in range(N - 2, -1, -1):
    Ai = A[i + 1]
    for j in range(max_j):
        c[(j, Ai >> j & 1)] += 1
    Ai = A[i]
    for j in range(max_j):
        ans += (1 << j) * c[(j, (Ai >> j & 1 ^ 1))]
        ans %= MOD
print(ans)


### FIXED CODE ###

from collections import defaultdict

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

max_A = max(A)
j = 0
while max_A >> j > 0:
    j += 1
max_j = j

ans = 0
MOD = 10 ** 9 + 7
for j in range(max_j):
    c = [0] * 2
    for i in range(N):
        c[A[i] >> j & 1] += 1
    ans += c[0] * c[1] * (1 << j)
    ans %= MOD
print(ans)
### BUGGY CODE ###

N=int(input())
number=list(map(int,input().split()))
sum_number=sum(number)
Q=int(input())
number_count=[0]*100001
for i in range(100001):
    number_count[i]=number.count(i)

for _ in range(Q):
    B,C=map(int,input().split())
    sum_number += (C-B)*number_count[B]
    number_count[C] += number_count[B]
    number_count[B] -= number_count[B]
    print(sum_number)


### FIXED CODE ###

from collections import Counter
N=int(input())
number=list(map(int,input().split()))
sum_number=sum(number)
Q=int(input())
number_count=Counter(number)


for _ in range(Q):
    B,C=map(int,input().split())
    sum_number += (C-B)*number_count[B]
    number_count[C] += number_count[B]
    number_count[B] = 0
    print(sum_number)