Harryxun/stf_run huggingface dataset:
c=0
for W in iter(input,'0\n'):
 c+=1
 W=int(W)
 dp=[0]*-~W
 for _ in[0]*int(input()):
  v,w=map(int,input().split(','))
  for i in range(W,w-1,-1):
   if dp[i]<dp[i-w]+v:dp[i]=dp[i-w]+v
 for i in range(W+1):
  if dp[W]==dp[i]:print(f'Case {c}:\n{dp[W]}\n{i}');break


### FIXED CODE ###

def f():
 c=0
 for W in iter(input,'0'):
  c+=1
  W=int(W)
  d=[0]*-~W
  for _ in[0]*int(input()):
   v,w=map(int,input().split(','))
   for i in range(W,w-1,-1):
    if d[i]<d[i-w]+v:d[i]=d[i-w]+v
  print(f'Case {c}:\n{d[W]}\n{d.index(d[W])}')
f()
import sys

N=int(input())
A=list(map(int,input().split()))
A.sort()
for i in range(N):
  if(A[i]==A[i+1]):
    print("NO")
    sys.exit()
print("YES")

### FIXED CODE ###

import sys

N=int(input())
A=list(map(int,input().split()))
A.sort()
for i in range(N-1):
  if(A[i]==A[i+1]):
    print("NO")
    sys.exit()
print("YES")
#### C
from functools import reduce
from operator import mul
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7
def fib(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)
   
a.append(n+1)
cnt = []
prev = 0
for i in a:
    tmp = fib(i+1-prev)
    cnt.append(tmp)
    prev = i+1
    
print(reduce(mul,cnt)%MOD)

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
MOD = 1000000007
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
        
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
        
print(dp[n])
# #バブルソート
# def BubbleSort(C,N):
#     for i in range (0,N,1):
#         for j in range(N-1,i-1,-1):
#             if int(C[j][1:2]) < int(C[j-1][1:2]):
#                 tmp = C[j]
#                 C[j] = C[j-1]
#                 C[j-1] = tmp
#     print(' '.join(C))

#バブルソート
def BubbleSort(C,N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1,0,-1):
            if int(C[j][1:2]) < int(C[j-1][1:2]):
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
                flag = 1
    print(' '.join(C))
    
    
                
                
#選択ソート
def SelectionSort(C,N):
    for i in range(0,N,1):
        minj = i
        for j in range(i,N,1):
            if int(C[j][1:2]) < int(C[minj][1:2]):
                minj = j
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    print(' '.join(C))
        
#安定かどうかの判定
def isStable(inp, out,N):
    for i in range(0,N):
        for j in range(i+1,N):
            for a in range(0,N):
                for b in range(a+1,N):
#                     print("inp(i,j):",inp[i],inp[j],"out(b,a):",out[b],out[a]+"\n")
                    if int(inp[i][1]) == int(inp[j][1]) and inp[i] == out[b] and inp[j] == out[a]:
                        print('Not stable')
                        return
    print('Stable')



愚直に調べるパターン
N = int(input())
A = list(input().split())
Bubble_A = A.copy()
Selection_A = A.copy()

BubbleSort(Bubble_A,N)
isStable(A,Bubble_A,N)
SelectionSort(Selection_A,N)
isStable(A,Selection_A,N)



### FIXED CODE ###

#バブルソート
def BubbleSort(C,N):
    for i in range (0,N,1):
        for j in range(N-1,i,-1):
            if int(C[j][1:2]) < int(C[j-1][1:2]):
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    print(' '.join(C))

    
                
#選択ソート
def SelectionSort(C,N):
    for i in range(0,N,1):
        minj = i
        for j in range(i,N,1):
            if int(C[j][1:2]) < int(C[minj][1:2]):
                minj = j
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    print(' '.join(C))



N = int(input())
A = list(input().split())
Bubble_A = A.copy()
Selection_A = A.copy()

BubbleSort(Bubble_A,N)
print("Stable")
SelectionSort(Selection_A,N)
flag = True
for Bubble,Selection in zip(Bubble_A,Selection_A):
    if Bubble != Selection:
        flag = False
if flag :
    print("Stable")
else:
    print("Not stable")
import math

def solution(n, a):
    gcd_left = [0]
    gcd_right = [0]
    for i in range(n):
        gcd_left.append(math.gcd(gcd_left[i], a[i]))
        # 順に(0とa[-1]), (a[-1]とa[-2]),...の比較
        # 要は右端から順にgcdを求めている
        gcd_right.append(math.gcd(gcd_right[i], a[-(i + 1)]))

    gcd_right = gcd_right[::-1]  # gcd_right[i]がi番目以降のgcdとなるように反転

    ans = []
    for i in range(n):
        ans.append(math.gcd(gcd_left[i], gcd_right[i + 1]))


    return max(ans)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(solution(n, a))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import unittest
import fractions


def solution(n, a):
    gcd_left = [0]
    gcd_right = [0]
    for i in range(n):
        gcd_left.append(fractions.gcd(gcd_left[i], a[i]))
        # 順に(0とa[-1]), (a[-1]とa[-2]),...の比較
        # 要は右端から順にgcdを求めている
        gcd_right.append(fractions.gcd(gcd_right[i], a[-(i + 1)]))

    gcd_right = gcd_right[::-1]  # gcd_right[i]がi番目以降のgcdとなるように反転

    ans = []
    for i in range(n):
        ans.append(fractions.gcd(gcd_left[i], gcd_right[i + 1]))


    return max(ans)


class MyTestCase(unittest.TestCase):
    def test1(self):
        self.assertEqual(solution(3, [7, 6, 8]), 2)

    def test2(self):
        self.assertEqual(solution(3, [12, 15, 18]), 6)

    def test3(self):
        self.assertEqual(solution(2, [1000000000, 1000000000]), 1000000000)




if __name__ == '__main__':

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

    unittest.main()
n=int(input())
ans='Yes'
t,a,b=map(int,input().split())
if (a+b)<t or (a+b-t)%2==1:
  ans='No'
for i in range(n):
  u,x,y=map(int,input().split())
  if (u-t)<abs(x-a)+abs(y-b) or ((u-t)-abs(x-a)-abs(y-b))%2==1:
    ans='No'
    break
  t,a,b=u,x,y
print(ans)

### FIXED CODE ###

n=int(input())

a,b,c=0,0,0

for i in range(n):
  x,y,z=map(int,input().split())
  dist=abs(b-y)+abs(c-z)
  if dist>x-a or (dist-(x-a))%2==1:
    print('No')
    exit()
    
  else:
    a,b,c=x,y,z
    continue
    
print('Yes')
a

### FIXED CODE ###

a=input()
b=input()
h=input()
a=int(a)
b=int(b)
h=int(h)
print (int((a+b)*h/2))
n,W=map(int,input().split())
dp=[0]*(W+1)
for _ in [0]*n:
    w,v=map(int,input().split())
    for i in range(W,w-1,-1):
        dp[i]=max(dp[i],dp[i-w]+v)
print(dp[-1])

### FIXED CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
l1,l2,l3,l4=[],[],[],[]
a=l[0][0]
for i in range(n):
    if l[i][0]==a:
        l1.append(l[i][1])
    elif l[i][0]==a+1:
        l2.append(l[i][1])
    elif l[i][0]==a+2:
        l3.append(l[i][1])
    else:
        l4.append(l[i][1])
l1.sort(reverse=True)
l2.sort(reverse=True)
l3.sort(reverse=True)
l4.sort(reverse=True)
ans=0
for h in range(len(l1)+1):
    for i in range(len(l2)+1):
        for j in range(len(l3)+1):
            for k in range(len(l4)+1):
                if a*h+(a+1)*i+(a+2)*j+(a+3)*k<=w:
                    ans=max(ans,sum(l1[:h])+sum(l2[:i])+sum(l3[:j])+sum(l4[:k]))
print(ans)
l=[]
for i in range(1,n+1):
  l.append(abs(l-1+i))
mi=l.index(min(l))
print(n*(l-1)+sum(range(1,n+1))-l-mi)

### FIXED CODE ###

n,l=map(int,input().split())
s=0
list=[]
for i in range(1,n+1):
  s+=i
  list.append(abs(l+i-1))
sum=n*(l-1)+s
m=list.index(min(list))
print(sum-l-m)
N,M = map(int,input().split())
N_list = [0]*N
flg_list  = [0]*N
flg = False
for i in range(M):
    s,c = map(int,input().split())
    if flg_list[s-1] == 0:
        N_list[s-1] = c
        flg_list[s-1] = 1
    elif N_list[s-1] != c:
        flg = True
        break
res = 0
for i in range(N-1,-1,-1):
    res += 10**i * N_list[N-1-i]

if N = 1:
    print(res)
elif flg or (N_list[0] == 0 and flg_list[0] == 1):
    print("-1")
elif N == len(str(res)):
    print(res)
else:
    print(res+10**(N-1))


### FIXED CODE ###

N,M = map(int,input().split())
N_list = [0]*N
flg_list  = [0]*N
flg = False
for i in range(M):
    s,c = map(int,input().split())
    if flg_list[s-1] == 0:
        N_list[s-1] = c
        flg_list[s-1] = 1
    elif N_list[s-1] != c:
        flg = True
        break
res = 0
for i in range(N-1,-1,-1):
    res += 10**i * N_list[N-1-i]

if N == 1 and not flg:
    print(res)
elif flg or (N_list[0] == 0 and flg_list[0] == 1):
    print("-1")
elif N == len(str(res)):
    print(res)
else:
    print(res+10**(N-1))
N, Q = map(int, input().split())
tree = [list(map(int, input().split())) for i in range(N-1)]
counter = [list(map(int, input().split())) for i in range(Q)]
dic = {}
for i in tree:
  try:
    dic[i[0]].append(i[1])
  except KeyError:
    dic[i[0]] = [i[1]]
keys = dic.keys()
for i in tree:
  if i[1] not in keys:
    dic[i[1]] = []
q = {i: 0 for i in dic.keys()}
 
def child_sum(q,v, child):
  if child == []:
    #print('test', q, v, child)
    return q
  else:
    for j in child:
      
      q[j] += v
      child = dic[j]
      #print('test2', j, v, child)
      q = child_sum(q, v, child)
  return q
    
for i, v in counter:
  q[i] += v
  child = dic[i]
  #print(q, i, child)
  q = child_sum(q, v, child)
print(' '.join([str(i) for i in q.values()]))


### FIXED CODE ###

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
q = [0 for i in range(N)]
 
for i in range(N-1):
  a, b = map(int, input().split())
  edge[a-1].append(b)
for i in range(Q):
  a, v = map(int, input().split())
  q[a-1] += v
 
for i, v in enumerate(q):
  #print(i, v)
  for j in edge[i]:
    #print(j)
    q[j-1] += v
print(*q)
from sys import stdin
input = stdin.readline

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

maxpoint = 0

for i in reversed(range(n+1)):
    if i % (b-1) == 0:
        tmp = int((a * i) / b)  - a * int(i/b) 
        maxpoint = max(tmp,maxpoint)
        print(maxpoint)
        exit()
    tmp = int((a * i) / b)  - a * int(i/b) 
    maxpoint = max(tmp,maxpoint)

print(maxpoint)



### FIXED CODE ###

from sys import stdin
input = stdin.readline
 
a,b,n = map(int,input().split())
maxpoint = 0
 
if b > n  :
    tmp = int((a * n) / b)  - a * int(n/b) 
    maxpoint = max(tmp,maxpoint)
else:
    k = int(n/b)*b -1
    maxpoint =  int((a * k) / b)  - a * int(k/b) 
    if b == 1:
        maxpoint = 0
 
print(maxpoint)
def palindromeQ(num):
  if num%10==num//10000:
    if (num%100)//10==(num//1000)%10:
      return(1)
    else:
      return(0)
  else:
    return(0)
ans=0
for i in range(A,B+1):
  ans+=palindromeQ(i)
print(ans)
  

### FIXED CODE ###

def palindromeQ(num):
  if num%10==num//10000:
    if (num%100)//10==(num//1000)%10:
      return(1)
    else:
      return(0)
  else:
    return(0)
ans=0
A,B=[int(s) for s in input().split()]
for i in range(A,B+1):
  ans+=palindromeQ(i)
print(ans)
import numpy as np

num = [] #５個の料理の必要時間
total = 0
mini = 10
for i in range(5): #入力
    a = input()
    a = int(a)
    b = a % 10 #bにはaの１の桁が０になったものが入る
    total += a - b + 10
    if b == 0:
        total -=10
    else:
        if b < mini:
            mini=b

total -=10
if mini= 10:
    print(total)
else:
    print(total + mini)

### FIXED CODE ###

import numpy as np

num = [] #５個の料理の必要時間
total = 0
mini = 10
b = 1
for i in range(5): #入力
    a = input()
    a = int(a)
    b = a % 10 #bにはaの１の桁が０になったものが入る
    total += a - b
    if b != 0:
        total+=10
        if b < mini:
            mini=b


if mini== 10:
    print(total)
else:
    print(total -(10-mini))
n = int(input())+1
l1 = range(1,n+1)
l2 = list(l1[1:n-1])
l2.append(1)
total = 0
for a,b in zip(l1,l2):
    total += a%b
print(total)

### FIXED CODE ###

n = int(input())
print((n)*(n-1)//2)
N,K = map(int,input().split())
S = list(map(int,input()))
blobs = []
if S[0] == 0:
    blobs.append(0)
cnt = 0
past_i = 0
for i in range(len(S)):
    if i == 0:
        past_i = S[i]
    if past_i == S[i]:
        cnt += 1
        past_i = S[i]
        
    else:
        blobs.append(cnt)
        cnt = 1
        past_i = S[i]
    if i == len(S)-1:
        blobs.append(cnt)

if S[-1] == 0:
    blobs.append(0)
print(blobs)
sums = []
for i in range(len(blobs)//2-K+1):
    temp_sum = sum(blobs[2*i:min(2*(i+K)+1,len(blobs))])
    sums.append(temp_sum)
    if temp_sum == N:
        break
print(max(sums))

### FIXED CODE ###

N,K = map(int,input().split())
S = input()
one = [0]
zero = [0]
if S[0] == '0':
    one.append(0)
cnt = 1
for i in range(1,len(S)):
    if S[i] != S[i-1]:
        if S[i-1] == '1':
            one.append(cnt+one[-1])                
        else:
            zero.append(cnt+zero[-1])                
        cnt = 1
    else:
        cnt += 1
else:
    if S[-1] == '1':
        one.append(cnt+one[-1])                
    else:
        zero.append(cnt+zero[-1])                
        one.append(one[-1])                
window_size = min(len(zero)-1,K)
MAX = 0
for i in range(len(zero)-window_size):
    if MAX < (zero[i+window_size] - zero[i]) + (one[i+window_size+1] - one[i]):
        MAX = (zero[i+window_size] - zero[i]) + (one[i+window_size+1] - one[i])

print(MAX)
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

CB = []
for _ in range(M):
  b,c = map(int,input().split())
  CB.append([c,b])
CB.sort(reverse=True)

num = 0
ans = 0 
for c,b in CB:
  for bi in range(b):
    if num > N or c<=A[num]:
      break
    else:
      num += 1
      ans += c
print(ans+sum(A[num:]))

### FIXED CODE ###

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

CB = []
for _ in range(M):
  b,c = map(int,input().split())
  CB.append([c,b])
CB.sort(reverse=True)

num = 0
ans = 0 
for c,b in CB:
  for bi in range(b):
    if num >= N: break
    if num > N or c<=A[num]:
      break
    else:
      num += 1
      ans += c
print(ans+sum(A[num:]) if num != N else ans)
a=int(input())
b=list(map(int,input().split()))
c=0
m=0
for i in b:
    c+=i
d=c/len(b)
e=str(d)[2]
e=int(e)
if e>=5:
    f=int(str(d)[0])+1
else:
    f=int(str(d)[0])
for g in b:
    m+=(abs(g-f))**2
print(m)



### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int(b)
if a>=10:
    print(b)
else:
    c=b-100*a+1000
    print(c)
#!/usr/bin/env python3

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

def gcd(a, b):
    if a > b:
        a, b = b, a
    # assert(a <= b)
    if b%a == 0:
        return a
    else:
        return gcd(b%a, a)

def gcd_many(l):
    # if len(l) == 1:
    #     return l
    # elif len(l) == 2:
    #     return gcd(l[0], l[1])
    # else:
    #     return gcd(l[0], gcd_many(l[1:]))
    if len(l) == 1:
        return l
    g = l[0]
    for i in range(1,len(l)):
        g = gcd(g, l[i])
    return g

Amax = max(A)
g = gcd_many(A)

possible = "POSSIBLE"
impossible = "IMPOSSIBLE"


if K > Amax:
    print(impossible)
else:
    if K % g == 0:
        print(possible)
    else:
        print(impossible)


### FIXED CODE ###

#!/usr/bin/env python3

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

def gcd(a, b):
    if a > b:
        a, b = b, a
    # assert(a <= b)
    if b%a == 0:
        return a
    else:
        return gcd(b%a, a)

def gcd_many(l):
    # if len(l) == 1:
    #     return l
    # elif len(l) == 2:
    #     return gcd(l[0], l[1])
    # else:
    #     return gcd(l[0], gcd_many(l[1:]))
    if len(l) == 1:
        return l[0]
    g = l[0]
    for i in range(1,len(l)):
        g = gcd(g, l[i])
    return g

Amax = max(A)
g = gcd_many(A)

possible = "POSSIBLE"
impossible = "IMPOSSIBLE"


if K > Amax:
    print(impossible)
else:
    if K % g == 0:
        print(possible)
    else:
        print(impossible)
import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
	break
    a[i] = l[i]
print(sum(a))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
x1 = list(map(int,input().rstrip().split(" ")))
x2 = list(map(int,input().rstrip().split(" ")))

def makey(x1,x2):
  total = 0
  for i in range(x1[0]):
    total += x2[i]
    if total > x1[1]:
      return i
y = makey(x1,x2)
print(y+1)

### FIXED CODE ###

x1 = list(map(int,input().rstrip().split(" ")))
x2 = list(map(int,input().rstrip().split(" ")))

def makey(x1,x2):
  total = 0
  for i in range(x1[0]):
    total += x2[i]
    if total > x1[1]:
      return i
  return i+1
y = makey(x1,x2)
print(y+1)
import sys
import math
from fractions import gcd
import numpy as np
readline = sys.stdin.readline
INF = 10**9


def main():
  N, M = map(int, readline().split())
  X = np.array(readline().split(), dtype=np.int64)
  X.sort()
  X = np.diff(X)
  X.sort()
  if M-N>=0:
    answer = X[:M-N].sum()
  else:
    answe = 0
  print(answer)
  
  
  
  
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
import math
from fractions import gcd
import numpy as np
readline = sys.stdin.readline
INF = 10**9


def main():
  N, M = map(int, readline().split())
  X = np.array(readline().split(), dtype=np.int64)
  X.sort()
  X = np.diff(X)
  X.sort()
  if M-N>=0:
    answer = X[:M-N].sum()
  else:
    answer = 0
  print(answer)
  
  
  
  
  
if __name__ == "__main__":
  main()
want = int().input()
due = int().input()
start = int().input()
over = int().input()
e = want - due
yen = 0
if e <= 0:
    for i in range(want):
        yen += start
 
if e > 0:
    for i in range(due):
        yen += start
    for j in range(e):
        yen += over
print(yen)

### FIXED CODE ###

want = int(input())
due = int(input())
start = int(input())
over = int(input())
e = want - due
yen = 0
if e <= 0:
    for i in range(want):
        yen += start

if e > 0:
    for i in range(due):
        yen += start
    for j in range(e):
        yen += over
print(yen)
n,s=int(input())
if n*2<=s+1:
  print(s-n+1)
else:
  print(-1)

### FIXED CODE ###

n = int(input())
s = int(input())
x = int(n**0.5)+1
def dsum(x,t):
  ret = 0
  while x>0:
    ret += x%t
    x //= t
  return ret
for i in range(2,x+1):
  if dsum(n,i) == s:
    print(i)
    exit()
for i in range(x,0,-1):
  if (n-(s-i))%i == 0:
    digit = (n-(s-i))//i
    if 0 < i < digit and 0 <= s-i < digit:
      print((n-(s-i))//i)
      exit()
if n == s:
  print(n+1)
  exit()
print(-1)
K,N=int(map(int,input().split()))
A=list(map(int,input().split()))
m=K
for j in range(len(a)):
  m=min(m,min(K-abs(A[j]-A[j-1]),K-abs(A[j]-A[j+1])))
print(m)
              
                                              


### FIXED CODE ###

S=str(input())
if S[2]==S[3] and S[4]==S[5]:
  print("Yes")
else:
  print("No")
n = int(input())
s,t = map(list,input().split())
ans = []
for i in range(n)
  ans.append(s[i])
  ans.append(t[i])
print(''.join(ans))

### FIXED CODE ###

n = int(input())
s1, s2 = map(list, input().split())

s = ''
for i in range(n):
  s = s + s1[i]
  s = s + s2[i]

print(s)
n = int(input())
num = 0
for _ in range(n):
    num += 1 / int(input())
print(1 / num)

### FIXED CODE ###

n = int(input())
nums = map(lambda x: 1 / int(x), input().split(' '))
print(1 / sum(nums))
A, B = map(int, input().split())
if b%a == 0:
    print(A+B)
else:
    print(B-A)

### FIXED CODE ###

A, B = map(int, input().split())
if B%A == 0:
    print(A+B)
else:
    print(B-A)
N, M = map(int, input().split())
A = [0 for i in range(N + 2)]
A[0] = 0
A[1] = 1
for i in range(M):
    a = int(input()) + 1
    A[a] = -1
for i in range(2, N+2):
    if A[i] ==  -1:
        A[i] = 0
    else:
        A[i] = A[i-1]+ A[i-2]
        A[i] = A[i] % 1000000007
    #print(A)
print(A[N + 1])





### FIXED CODE ###

P = list(map(int, input().split()))
P.sort()
print(P[0]+  P[1])
n,m=map(int, input().split())

roads=[]

for _ in range(m):
  a,b=map(int, input().split())
  roads.append([a,b].sort())
  
group=[i for i in range(n)]

group2=[]

while group2!=group:
  group2=group
  for road in roads:
    group[road[1]]=group[road[0]]

print(group[-1])  
      

### FIXED CODE ###

class UnionFind:
    from typing import List, Set

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n

    def merge(self, x, y) -> int:
        x = self.leader(x)
        y = self.leader(y)

        if x == y:
            return 0

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

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

        return self.parent[x]

    def same(self, x, y) -> bool:
        return self.leader(x) == self.leader(y)

    def leader(self, x) -> int:
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.leader(self.parent[x])
            return self.parent[x]

    def size(self, x) -> int:
        return -self.parent[self.leader(x)]

    def groups(self) -> List[Set[int]]:
        groups = dict()

        for i in range(self.n):
            p = self.leader(i)
            if not groups.get(p):
                groups[p] = set()
            groups[p].add(i)

        return list(groups.values())


def main():
    N, M = map(int, input().split())

    uf = UnionFind(N)

    for _ in range(M):
        # UnionFindを0スタートで実装しているので、入力から1引きます
        A, B = map(lambda x: int(x) - 1, input().split())  
        uf.merge(A, B)  # AとBをmergeします。union, uniteとも呼ばれます。

    print(len(uf.groups()) - 1)


if __name__ == '__main__':
    main()
from collections import deque
s = input()
n = len(s)

deque = deque()
deque.append(0)

def str_plus(i):
    s1 = s[i]
    if s1 == "d":
        if s[i:i+5] == "dream":
            if s[i+5:i+7] == "er":
                return [i+5,i+7]
            else:
                return [i+5]
    if s1 == "e":
        if s[i:i+5] == "erase":
            if s[i+5] == "r":
                return [i+5,i+6]
            else:
                return [i+5]

ans = "NO"

while deque:
    i = deque.pop()
    if i == n:
        ans = "YES"
        break
    l = str_plus(i)
    if l != None:
        deque.extend(l)

print(ans)

### FIXED CODE ###

s = input()[::-1]
l = [ 'dream', 'dreamer', 'erase', 'eraser']
for i in range(4):
	s1 = l[i][::-1]
	l[i] = s1

n = len(s)
i = 0
t = tuple(l)

while i < n:
	judge = 0
	s_l = []
	for j in (5,6,7):
		if n-i >= j:
			s1 = s[i:i+j]
			if s1 in t:
				i += j
				judge = 1
	
	if judge == 0:
		break

if i == n:
	print('YES')
else:
	print('NO')
a = list(input().split(''))

for i in a:
    if i == "a":
        c1 = 1
    elif i == "b":
        c2 = 1
    elif i == "c":
        c3 = 1

if c1 == 1 and c2 == 1 and c3 == 1:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

a = list(input())
if a[0] == a[1] or a[1] == a[2] or a[2] == a[0]:
    print("No")
else:
    print("Yes")
li_1 = list(map(int,input().split()))
N = li_1[0]
K = li_1[1]

D = list(map(int,input().split()))


minvalue=N
temp=0

for i in range(10*N):
    i=i+N
    numtemp=i
    num_4=int(i/10000)
    i=i-10000*num_4
    num_3=int(i/1000)
    i=i-1000*num_3
    num_2=int(i/100)
    i=i-100*num_2
    num_1=int(i/10)
    i=i-10*num_1
    num_0=i
    
    for j in range(K):
        if (num_0!=D[j])and(num_1!=D[j])and(num_2!=D[j])and(num_3!=D[j])and(num_4!=D[j]):
            temp+=1
            
    if temp==K:
        num=numtemp
        break
    
    temp=0

print(num)
    

### FIXED CODE ###

li_1 = list(map(int,input().split()))
N = li_1[0]
K = li_1[1]

D = list(map(int,input().split()))


minvalue=N
temp=0

for i in range(10*N):
    i=i+N
    numtemp=i
    if numtemp>=10000:
        num_4=int(i/10000)
        i=i-10000*num_4
    else:
        num_4=10
        
    if numtemp>=1000:
        num_3=int(i/1000)
        i=i-1000*num_3
    else:
        num_3=10
        
    if numtemp>=100:
        num_2=int(i/100)
        i=i-100*num_2
    else:
        num_2=10
        
    if numtemp>=10:
        num_1=int(i/10)
        i=i-10*num_1
    else:
        num_1=10
        
    num_0=i
    
    for j in range(K):
        if (num_0!=D[j])and(num_1!=D[j])and(num_2!=D[j])and(num_3!=D[j])and(num_4!=D[j]):
            temp+=1
            
    if temp==K:
        num=numtemp
        break
    
    temp=0

print(num)