Harryxun/stf_run huggingface dataset:
from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20
n, k = map(int, input().split())

clst = []
rlst = []

for i in range(n):
  c, r = map(int, input().split())
  clst.append(c)
  rlst.append(r)

edges = [[0] * n for i in range(n)]

for i in range(k):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  edges[a][b] = edges[b][a] = 1

costs = [INF for i in range(n)]
costs[0] = 0

def make_to_lst(s_num):
  loop = rlst[s_num]
  temp = {i for i in range(n) if edges[s_num][i]}
  ret = {i for i in temp}
  while loop - 1:
    new = set()
    for p in temp:
      pto = {i for i in range(n) if edges[p][i]}
      new = new | pto
    ret = ret | temp
    temp = new - ret
    loop -= 1
  return ret

costs[0] = 0
break_flag = 0
que = [(clst[0], 0)]

while que and not break_flag:
  next_cost, s_num = pop(que)
  to_lst = make_to_lst(s_num)
  
  for num in to_lst:
    if costs[num] > next_cost:
      costs[num] = next_cost
    if num == n - 1:
      break_flag = 1
      break
    push(que, (next_cost + clst[num], num))

print(costs[n - 1])


### FIXED CODE ###

from heapq import heappop as pop
from heapq import heappush as push

def main():
  n, k = map(int, input().split())
  
  clst = []
  rlst = []
  
  for i in range(n):
    c, r = map(int, input().split())
    clst.append(c)
    rlst.append(r)
  
  edges = [[] * n for i in range(n)]
  
  for i in range(k):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
  
  costs = [None] * n
  used = [False] * n
  
  def make_to_lst(s_num):
    loop = rlst[s_num]
    temp = set(edges[s_num])
    ret = set()
    while loop and temp:
      new = set()
      for p in temp:
        pto = set(edges[p])
        new = new | pto
      ret = ret | temp
      temp = new - ret
      loop -= 1
    return ret
  
  used[0] = True
  costs[0] = 0
  que = [(clst[0], 0)]
  
  while que:
    next_cost, s_num = pop(que)
    to_lst = make_to_lst(s_num)

    for num in to_lst:
      if num == n - 1:
        print(next_cost)
        return

      costs[num] = next_cost

      if not used[num]:
        push(que, (next_cost + clst[num], num))
        used[num] = True
  

main()
a, b, c = map(int, input().split)

if a > b + c:
  print(0)
else:
  print(c-b)

### FIXED CODE ###

a, b, c = map(int, input().split())

if a > b + c:
  print(0)
else:
  print(c+b-a)
s=list(input())
from itertools import product, permutations,combinations


#l = len(s) +1
#A = [i for i in range(len(s)+1)]

cnt = 0
ans = []

for i in combinations([i for i in range(len(s)+1)],2):
    
    ans = s[i[0]:i[1]]
    if int("".join(map(str, ans)))%2019==0:
            cnt +=1
    
        
print(cnt)
            

### FIXED CODE ###

S,W= map(int,input().split())

if W>=S:
    print("unsafe")
else:
    print("safe")
S = list(input())
K = int(input())
 
ans = 0
#２つ並べて一般性を確かめる
S2 = S*2

for i in range(1,len(S2)):
    if S2[i-1]== S2[i]:
        s_d[i] = '@'
        #2回目以降はk-1回任意の@へ直す
        if i>=len(S2)//2:
            ans+= K-1
        else:
            ans+=1

print(ans) 

### FIXED CODE ###

S = list(input())
K = int(input())
 
ans = 0
#２つ並べて一般性を確かめる
S2 = S*2

for i in range(1,len(S2)):
    if S2[i-1]== S2[i]:
        S2[i] = '@'
        #2回目以降はk-1回任意の@へ直す
        if i>=len(S2)//2:
            ans+= K-1
        else:
            ans+=1
            
if len(set(S)) ==1 and len(S)%2 !=0:
   ans = len(S)*(K//2)+(K%2==1)*(len(S)//2)
print(ans)
import math
import sys
N, X = map(int, input().split())

dis_list = [abs(int(i) - X) for i in input().split()]
if len(dis_list) < 2:
    print(dis_list[0])
    sys.exit()


first_gc = math.gcd(dis_list[0], dis_list[1])

for i in range(len(dis_list)):
    first_gc = math.gcd(first_gc, dis_list[i])

print(first_gc)

### FIXED CODE ###

import fractions as math
import sys
N, X = map(int, input().split())

dis_list = [abs(int(i) - X) for i in input().split()]
if len(dis_list) < 2:
    print(dis_list[0])
    sys.exit()


first_gc = math.gcd(dis_list[0], dis_list[1])

for i in range(len(dis_list)):
    first_gc = math.gcd(first_gc, dis_list[i])

print(first_gc)
N,X = map(int,input().split())
ingredients = []
for i in range(N):
    m = int(input())
    ingredients.append(m)
print(N+(X - sum(m)) // min(m))

### FIXED CODE ###

N,X = map(int,input().split())
ingredients = []
for i in range(N):
    m = int(input())
    ingredients.append(m)
print(N+(X - sum(ingredients)) // min(ingredients))
import math
n, x = map(int, input().split())
a = list(map(int, input().split()))
a.append(x)
a = sorted(a)
t = 0
for i in range(n-1):
    if i == 0:
        t = a[1] - a[0]
    else:
        t = math.gcd(t, a[i + 1] - a[i])
print(t)

### FIXED CODE ###

from fractions import gcd
N, X = map(int, input().split())
kotae = list(map(int, input().split()))
kotae.append(X)
kotae.sort()
t = kotae[1]-kotae[0]
for i in range(len(kotae)-1):
    t = gcd(t, abs(kotae[i + 1] - kotae[i]))
print(t)
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,k = iim()
A = iil()
d = {0:True}
l = [0]
def move(num):
    l.append(A[num]-1)
    if d.get(A[num]-1,False):
        return True if A[num]-1 == 0 else False
    else:
        d[A[num]-1] = True
        return move(A[num]-1)

if move(0):
    rep = len(l)-1
    ini = 0
else:
    ini = l.index(l[-1])
    rep = len(l)-ini-1
mod = (k-ini)%rep
if mod == 0:
    mod = rep
#print(l,mod,rep)
print(l[ini+mod]+1)

### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))
import sys 
sys.setrecursionlimit(10000000)


n,k = iim()
A = iil()
d = {0:True}
l = [0]
def move(num):
    l.append(A[num]-1)
    if d.get(A[num]-1,False):
        return True if A[num]-1 == 0 else False
    else:
        d[A[num]-1] = True
        return move(A[num]-1)

if move(0):
    rep = len(l)-1
    ini = 0
else:
    ini = l.index(l[-1])
    rep = len(l)-ini-1

if k <= ini:
    print(l[k]+1)
else:
    mod = (k-ini)%rep
    if mod == 0:
        mod = rep
#    print(l,mod,rep,ini)
    print(l[ini+mod]+1)
n = int(raw_input())

rt = [int(raw_input()) for x in xrange(n)]

i_max = rt.index(max(rt))
i_min = rt.index(min(rt))

a = rt[i_max] - min(rt[1:i_max])
b = max(rt[i_min:]) - rt[i_min]

print a if a > b else b

### FIXED CODE ###

n = int(raw_input())

_min, dif = 10**10, -10**10
for x in xrange(n):
    a = int(raw_input())
    if a -_min > dif:
        dif = a - _min
    if a < _min:
        _min = a
print dif
import math

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

res = 0.0
for i in range(1, n+1):
  if not (k//i) == 0:
    if (k/i) == (k//i):
    	if math.log2(k//i) == int(math.log2(k//i)):
      		x = int(math.log2(k//i))
    	else:
      	x = int(math.log2(k//i)) + 1
  	else:
     	x = int(math.log2(k//i)) + 1
  else:
    x = 0
  res += (1/n) * (0.5 ** x)
print(res)

### FIXED CODE ###

import math

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

res = 0.0
for i in range(1, n+1):
  if not (k//i) == 0:
    if (k/i) == (k//i):
      if math.log2(k//i) == int(math.log2(k//i)):
        x = int(math.log2(k//i))
      else:
        x = int(math.log2(k//i)) + 1
    else:
      x = int(math.log2(k//i)) + 1
  else:
    x = 0
  res += (1/n) * (0.5 ** x)
print(res)
n=int(input())

table=[0]*10**6

for i in range(n):
    a=int(input())
    table[a-1]+=1

ans=0

for j in range(10**6):
    if table[j]%2==1:
        ans+=1

print(ans)

### FIXED CODE ###

n=int(input())

a=[int(input()) for i in range(n)]

dic={}

for i in range(n):
    if a[i] not in dic:
        dic[a[i]]=1
    else:
        dic[a[i]]+=1

ans=0

for val in dic.values():
    if val%2==1:
        ans+=1

print(ans)
def how_many(n):
  count = 0
  while n%2==0:
    n /= 2
    count += 1
    return count

N = int(input())
A = map(int, input().split())
print(min(map(how_many, A)))

### FIXED CODE ###

a = str(input())
print(a.count('1'))
sys.setrecursionlimit(10**6)
edges = {}
p = []

def dfs(target_node, keisyo_point):
    global p
    p[target_node] += keisyo_point

    next_node = edges[target_node]

    if not next_node:
        return
    else:
        for next in next_node:
            dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    #edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
    p = [0] * (n + 1)
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1,0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
edges = {}
p = {}
done_nodes = set()

def dfs(target_node, keisyo_point):
    global p
    done_nodes.add(target_node)
    p[target_node] += keisyo_point
    next_node = edges[target_node]
    if not next_node:
        return
    else:
        for next in next_node:
            #edges[next].pop(edges[next].index(target_node))
            #dfs(next, p[target_node])
            if next in done_nodes:
                pass
            else:
                dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
    p = {e: 0 for e in range(1, n+1)}
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1, 0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

if __name__ == '__main__':
    main()
a,b = map(int,input().split())
c = 2*b
d = a-c
if a > c:
print(d)
elif a <= c:
print(0)

### FIXED CODE ###

a,b = map(int,input().split())
c = 2*b
d = a-c
if d > 0:
 print(d)
elif d <= 0:
 print(0)
A=list(map(int, input().split())) 
b=A[0]*A[1]
if b%2=0:
	print('Even')
else
	print('Odd')


### FIXED CODE ###

A=list(map(int, input().split()))
if A[0]*A[1]%2==0:
  print('Even')
else:
  print('Odd')
import math
#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))




def lcm(x, y):
    return (x * y) // math.gcd(x, y)


a,b=input2()

print(lcm(a,b))

### FIXED CODE ###

import math
import fractions
#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))




def lcm(x, y):
    return (x * y)//fractions.gcd(x, y)


a,b=input2()

print(lcm(a,b))
n = int(input())
memo = [-1] * (n+1)
import sys
sys.setrecursionlimit(10000)
def f(n):
    if n == 0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6 = 1
    pow9 = 1
    res = min(res, f(n - 1) + 1)
    while pow6*6 <= n:
        pow6 *= 6
        res = min(res, f(n - pow6) + 1)
        
    while pow9*9 <= n:
        pow9 *= 9
        res = min(res, f(n - pow9) + 1)
        
    memo[n] = res
    return res
print(f(n))


### FIXED CODE ###

n = int(input())
memo = [-1] * (n+1)
import sys
sys.setrecursionlimit(1000000)
def f(n):
    if n == 0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6 = 1
    pow9 = 1
    res = min(res, f(n - 1) + 1)
    while pow6*6 <= n:
        pow6 *= 6
        res = min(res, f(n - pow6) + 1)
        
    while pow9*9 <= n:
        pow9 *= 9
        res = min(res, f(n - pow9) + 1)
        
    memo[n] = res
    return res
print(f(n))
x,y,z=map(int,input().split())
print(f'{z} {x} {y}')



### FIXED CODE ###

x,y,z=map(int,input().split())
print('{0} {1} {2}'.format(z,x,y))
s=input()
if s=="SUN"
  print(7)
if s=="MON"
  print(6)
if s=="TUE"
  print(5)
if s=="WED"
  print(4)
if s=="THU"
  print(3)
if s=="FRI"
  print(2)
if s=="SAT"
  print(1)

### FIXED CODE ###

s=input()
if s=="SUN":
  print(7)
if s=="MON":
  print(6)
if s=="TUE":
  print(5)
if s=="WED":
  print(4)
if s=="THU":
  print(3)
if s=="FRI":
  print(2)
if s=="SAT":
  print(1)
n = int(input())
s = list(input())
count_b_l = 0
count_w_r = 0
for i in range(len(s)):
    if s[i] == '.':
        count_w_r += 1
result = []
for i in range(len(s)):
    if s[i] == '#':
        count_w_l += 1
    else:
        count_b_r -= 1
    result.append(count_b_l+count_w_r)
print(min(result))

### FIXED CODE ###

N=int(input())
S=input()
b=0
w=S.count(".")
ans=b+w
for s in S:
    if s=="#":
        b+=1
    else:
        w-=1
    ans=min(ans, b+w)
print(ans)
N=int(input())
s=[int(input()) for _ in range(N)]
ss = [s[i] for i in range(N) if s[i]%10!=0]
if sum(s)%10 != 0:
    print(sum(s))
else:
    print(sum(s)-min(ss))

### FIXED CODE ###

N=int(input())
s=[int(input()) for _ in range(N)]
ss = [s[i] for i in range(N) if s[i]%10!=0]
if sum(s)%10 != 0:
    print(sum(s))
else:
    if not ss:
        print(0)
    else:
        print(sum(s) - min(ss))
Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = int(input())
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(input())
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print(l[1] % Num)

### FIXED CODE ###

Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = -1
if M != 0:
  danger = int(input())
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(input())
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print(l[1] % Num)
x = int(input())
y = int(input())
print(x + (y//2))

### FIXED CODE ###

x, y =map(int, input().split())
print(x+y//2)
X,Y = map(int, input().split())
Y = 2/Y
print(int X + Y/2)

### FIXED CODE ###

X,Y = map(int, input().split())
print(int (X + Y/2))
num = int(input())
num_1 = num % 10
if num_1 == 2,4,5,7,9:
  print('hon')
elif num_1 == 0,1,6,8:
  print('pon')
else:
  print('bon')

### FIXED CODE ###

num = int(input())
num_1 = num % 10
if num_1 == 3:
  print('bon')
elif num_1 <= 1 or num_1 == 6 or num_1 == 8:
  print('pon')
else:
  print('hon')
A,B,C=map(int,input().split())

if A=B=C or A!=B!=C:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

A,B,C=map(int,input().split())

if A==B==C or A!=B!=C!=A:
  print("No")
else:
  print("Yes")
a=int(input())
b=int(input())
c=int(input())
x=int(input())

if x%500==0 and x%100==0:
    print((x//500)+(x//100)+1)
elif  x%500!=0 and x%100==0:
    print((x//100)+1)
else:
    print(1)


### FIXED CODE ###

X=int(input())
A=int(input())
B=int(input())

Y=(X-A)%B
print(Y)
x1,x2,y1,y2 = map(int,input().split())
x3 = x2 + (y1 - y2)
y3 = y2 + (x2 - x1)
x4 = y1 + (x2 - x1)
y4 = x1 + (y1 - y2)
print(x3,y3,x4,y4)

### FIXED CODE ###

# -*- coding: utf-8 -*-
K = int(input())
if K % 2 == 0:
  print((K//2)*(K//2))
elif K % 2 == 1:
  print(((K+1)//2)*((K-1)//2))
n,k=map(int,input().split())
m=map(str,input())
A=m[k-1]
for i in range(n):
    if m[i]==A:
        continue
        if m[i]!=A:
            m.replace(m[i],'*')
print(m)

### FIXED CODE ###

n,s,k=int(input()),input(),int(input()) #入力を順番に一気に定義する
A=s[k-1]
for i in range(n):
    if s[i]!=A:
        s=s.replace(s[i],'*')
print(s)
N=int(input())
List=list(map(int,input().split()))
a=0
for i in range (len(List)):
      a= a+(1/(List[i])
print (1/a)

### FIXED CODE ###

N=int(input())
List=list(map(int,input().split()))
a=0
for i in range (len(List)):
   a+= 1/(List[i])
print(1/a)
W,H,N = map(int,input().split())
x=[]
y=[]
a=[]

A1=[]
A2=[]
A3=[]
A4=[]

for n in range(N):
    i,j,k = map(int,input().split())
    x.append(i)
    y.append(j)
    a.append(k)
a1,a2,a3,a4 = 0,0,0,0

for n in range(N):
    if a[n] == 1:
        A1.append(x[n])
        a1 = a1 + 1
    elif a[n] == 2:
        A2.append(x[n])
        a2 = a2 + 1
    elif a[n] == 3:
        A3.append(y[n])
        a3 = a3 + 1
    else:
        A4.append(y[n])
        a4 = a4 + 1

if a1 == 0 and a2 == 0:
    width = W
elif a1 == 0:
    width = min(A2)
elif a2 == 0:
    width = W - max(A1)
else:
    width = min(A2) - max(A1)
    if width <0:
        width = 0

if a3 == 0 and a4 == 0:
    height == H
elif a3 == 0:
    height =min(A4)
elif a4 ==0:
    height = H-max(A3)
else:
    height =min(A4) - max(A3)
    if width <0:
        width = 0

print(height*width)


### FIXED CODE ###

W,H,N = map(int,input().split())

wl = 0
wr = W
hu = H
hl = 0

for i in range(N):
    x,y,a = map(int,input().split())
    if a == 1 and x > wl:
        wl = x
    elif a == 2 and x < wr:
        wr = x
    elif a == 3 and y > hl:
        hl =y
    elif a == 4 and y < hu:
        hu = y
    
if wl>wr or hl>hu:
    print(0)
else:
    print((wr-wl)*(hu-hl))
n,k = map(int,input().split())
a,p = [1],[1]
for i in range(n):
  a.append(a[i]*2+3)
  p.append(p[i]*2+1)
def f(n,k):
  if n == 0:
    if k == 0:
      return 0
    else:
      return 1
  if k == 0:
    return 0
  elif k <= a[n-1]+1:
    return f(n-1,k-1)
  elif k == p[n]:
    return p[n-1]+1
  elif k <= a[n]*2+3:
    return p[n-1]+1+f(n-1,k-2-a[n-1])
print(f(n,k))



### FIXED CODE ###

n,k = map(int,input().split())
a,p = [1],[1]
for i in range(n):
  a.append(a[i]*2+3)
  p.append(p[i]*2+1)
def f(n,k):
  if n == 0:
    if k == 0:
      return 0
    else:
      return 1
  if k == 0:
    return 0
  elif k <= a[n-1]+1:
    return f(n-1,k-1)
  else:
    return p[n-1]+1+f(n-1,k-2-a[n-1])
print(f(n,k))
A, B = map(int, input().split())
print(max([A*B, A+B, A-B])

### FIXED CODE ###

A, B = map(int, input().split())
print(max([A*B, A+B, A-B]))
n,k=map(int,input().split())
d={int(x) for x in input().split()}
e={0,1,2,3,4,5,6,7,8,9}
f=list(d^e)
ans=[]
for i in f:
    for j in f:
        for k in f:
            for l in f:
                ans.append(1000*i+100*j+10*k+l)
ans=[m for m in ans if m>= n]
print(min(ans))

### FIXED CODE ###

n,k=map(int,input().split())
s=set(input().split())
while True:
    l=list(str(n))
    for i in l:
        if i in s:
            break
    else:
        break
            
    n += 1
print(n)
# Belongs to : midandfeed aka asilentvoice
while(1):
	n = str(input())
	
	if n:
		ans = 0
		for x in n:
			ans += int(x)
		print(ans)
	else:
		break

### FIXED CODE ###

# Belongs to : midandfeed aka asilentvoice
while(1):
	n = str(input())
	
	if n != '0':
		ans = 0
		for x in n:
			ans += int(x)
		print(ans)
	else:
		break
A, B, N=list(map(int, input().split()))
if B > N:
    X = N
else:
    X = B-1

Ans = math.floor(A*X/B) - A * math.floor(X/B)
print(Ans)


### FIXED CODE ###

import math
A, B, N=list(map(int, input().split()))
if B > N:
    X = N
else:
    X = B-1

Ans = math.floor(A*X/B) - A * math.floor(X/B)
print(Ans)
N,K=[int(x) for x in input().rstrip().split()]
A=[int(x) for x in input().rstrip().split()]
stack=[]
done=[0 for i in range(N)]
done[0]=0
now=1
amari=[]
cnt=0
for i in range(10**5):
  done[now-1]+=1
  if done[now-1]==2:
    cnt+=1

  if done[now-1]==3:
    break
  
  stack.append(now)
  now=A[now-1]

ans=K%cnt
print(stack[ans])

### FIXED CODE ###

N,K=[int(x) for x in input().rstrip().split()]
A=[int(x) for x in input().rstrip().split()]

stack=[]
done=[0 for i in range(2*(10**5))]
done[0]=0
now=0
dou=[]

while(done[now]<2):
  
  if done[now]==0:
    stack.append(now)
  else:
    dou.append(now)
  done[now]+=1
  now=A[now]-1

if K<len(stack):
  print(stack[K]+1)
else:
  print(dou[(K-len(stack)-len(dou))%len(dou)]+1)
class UnionFind():
    def __init__(self, n):
        self.par = [-1]*n

    def root(self, x):
        if self.par[x] < 0:
            return x
        return self.root(self.par[x])

    def unite(self, x, y):
        if x > y:
            x, y = y, x
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx

    def size(self, x):
        return -self.par[self.root(x)]

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def return_par(self):
        return self.par

n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))
print(ans)


### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
t = dict()
for i in range(1, n+1):
    t[i] = set()
for a, b in ab:
    t[a].add(b)
    t[b].add(a)

q = deque()
s = set()
ans = 0
for i in range(1, n+1):
    if i not in s:
        q.append(i)
        s.add(i)
        tmp = [i]
        while q:
            v = q.popleft()
            for ti in t[v]:
                if ti not in s:
                    tmp.append(ti)
                    q.append(ti)
                    s.add(ti)
    ans = max(ans, len(tmp))
print(ans)
from collections import Counter
mod = 1000000007

n = int(input())
a_div_b = []
a_0 = 0
b_0 = 0
a_b_0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
        if a == 0:
            a_0 += 1
        if b == 0:
            b_0 += 1
        break
    if a * b < 0:
        a_div_b.append(a/b)
    else:
        a_div_b.append(b/a)

cnt = Counter(a_div_b)
cnt2 = sorted(cnt.items())
lst = []
total = 0
for num, _ in cnt2:
    if num > 0:
        break
    a1 = cnt[num]
    a2 = cnt[-num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 * b_0 != 0:
    total += a0 + b0
    lst.append([a0, b0])
n -= a_b_0
ans = pow(2, n - total, mod)
tmp = 1
for a, b in lst:
    tmp *= pow(2, a, mod) + pow(2, b, mod) - 1
ans = (ans * tmp - 1 + a_b_0) % mod
    
print(ans)
    


### FIXED CODE ###

from collections import defaultdict
from math import gcd
mod = 1000000007

n = int(input())
plus = defaultdict(int)
minus = defaultdict(int)
a_0 = 0
b_0 = 0
a_b_0 = 0
xxx = 10 ** 10
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
        elif a == 0:
            a_0 += 1
        else:
            b_0 += 1
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    if a * b < 0:
        minus[(abs(a), abs(b))] += 1
    else:
        plus[(abs(b), abs(a))] += 1

total = 0
lst = []
for num, _ in minus.items():
    a1 = minus[num]
    a2 = plus[num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 > 0 and b_0 > 0:
    total += a_0 + b_0
    lst.append([a_0, b_0])
n -= a_b_0
ans = pow(2, n - total, mod)
for a, b in lst:
    ans = (ans * (pow(2, a, mod) + pow(2, b, mod) - 1)) % mod
ans = (ans - 1 + a_b_0) % mod
    
print(ans)
ar = [0]*n

for i in range(n-1):
    ar[a[i]] += 1

tmp = ar.pop(0)
ar.append(tmp)
for i in range(n):
    print(ar[i])


### FIXED CODE ###

n  = int(input())
a = input().split()
a = [int(x) for x in a]
ar = [0]*n

for i in range(n-1):
    ar[a[i]] += 1

tmp = ar.pop(0)
ar.append(tmp)
for i in range(n):
    print(ar[i])
s = input()
N = len(s)
c=0
for i in range(N-1):
  if s[i]==s[N-1-i] and s[i]==s[(N-1)/2-1-i] and s[(N+3)/2-1+i]==s[N-1-i]:
    c+=1
    
if c == N:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

s = list(input())
n = (len(s)+1)//2
if s[:n-1] == s[len(s):n-1:-1] == s[n-2::-1]:
  print("Yes")
else:
  print("No")
n = int(input())
n_all = 10**(n) % mod
bad_0 = 9**(n)%mod
bad_9 = 9**(n)%mod
bad_18 = 8**(n)%mod

print(n_all-bad_0-bad_9+bad_18)

### FIXED CODE ###

n = int(input())
mod = (10**9)+7
n_all = 10**(n) % mod
bad_0 = 9**(n)%mod
bad_9 = 9**(n)%mod
bad_18 = 8**(n)%mod

print((n_all-bad_0-bad_9+bad_18)%mod)