Harryxun/stf_run huggingface dataset:
from collections import defaultdict

def adj(v):
    t = 1
    while t <= 2*10**9:
        if t > v:
            yield t-v
        t *= 2

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

cnt = defaultdict(int)
for a in A:
    cnt[a] += 1

degree = defaultdict(int)
for v in cnt.keys():
    for u in adj(v):
        if u == v:
            degree[v] += int(cnt.get(u,0) >= 2)
        else:
            degree[v] += int(cnt.get(u,0) >= 1)

stack = [v for v,c in degree.items() if c == 1]
res = 0
while stack:
    v = stack.pop()
    c = cnt.get(v,0)
    if c == 0:
        continue
    for u in adj(v):
        if u == v and cnt.get(u,0) >= 2:
            break
        elif cnt.get(u,0) >= 1:
            break
    res += 1
    del cnt[u]
    degree[u] -= 1
    if degree[u] == 1:
        stack.append(u)

print(res)

### FIXED CODE ###

from collections import defaultdict

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

cnt = defaultdict(int)

for a in A:
    cnt[a] += 1
res = 0
for x in reversed(A):
    y = (1 << x.bit_length()) - x
    if x == y:
        k = cnt[x]//2
    else:
        k = min(cnt[x], cnt[y])
    res += k
    cnt[x] -= k
    cnt[y] -= k

print(res)
n = int(raw_input())
def gb(s):
	bal,m = 0
	for l in s: 
		bal += 1 if l == '(' else -1
		m = min(m, bal)
	return (bal,m)


rs = [gb(raw_input()) for _ in range(n)]
rs.sort(key = lambda x: (0,-x[1], x[0]) if x[0]>=0 else (1,x[1] - x[0], -x[0]))

def f(rs):
	s = 0
	for aa,bb in rs:
		if s + bb < 0: return False
		s += aa
	return s == 0

print 'Yes' if f(rs) else 'No'

### FIXED CODE ###

n = int(raw_input())
def gb(s):
	bal = 0
	m = 0
	for l in s: 
		bal += 1 if l == '(' else -1
		m = min(m, bal)
	return (bal,m)


adds, dels = [], []
for _ in range(n):
	e = gb(raw_input())
	if e[0] >= 0:
		adds.append(e)
	else:
		dels.append(e)
adds.sort(key = lambda x: (-x[1], -x[0]))
dels.sort(key = lambda x: (x[1] - x[0], -x[0]))
def f(adds, dels):
	s = 0
	for aa,bb in adds:

		if s + aa < 0:
			return False
		if s + bb < 0:
			return False
		s += aa
		

	for aa,bb in dels:

		if s + aa < 0:
			return False
		if s + bb < 0:
			return False
		s += aa
	return s == 0

print 'Yes' if f(adds, dels) else 'No'
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

def AGC028A():
    N, M = map(int, input().split())
    S = input()
    T = input()
    if len(S) < len(T):
        S, T = T, S
    if lcm(N, M) == max(N, M) and S[0:len(T)] == T:
        print(-1)
        return 0
    key = lcm(N, M)
    n = key // N
    m = key // M
    n_list = []
    for i in range(0, key, n):
        n_list.append(i)
    m_list = []
    for j in range(0, key, m):
        m_list.append(j)
    i = 0
    j = 0
    while True:
        if i >= len(n_list) or j >= len(m_list):
            break
        if n_list[i] == m_list[j]:
            if S[i] != T[j]:
                print(-1)
                return 0
        if n_list[i] > m_list[j]:
            j += 1
        elif n_list[i] < m_list[j]:
            i += 1
        else:
            i += 1
            j += 1
    print(key)

AGC028A()

### FIXED CODE ###

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

def AGC028A():
    N, M = map(int, input().split())
    S = input()
    T = input()

    key = lcm(N, M)
    n = key // N
    m = key // M
    n_list = []
    for i in range(0, key, n):
        n_list.append(i)
    m_list = []
    for j in range(0, key, m):
        m_list.append(j)

    #print(n_list, m_list)
    i = 0
    j = 0
    while True:
        if i >= len(n_list) or j >= len(m_list):
            break
        if i >= len(S) or j >= len(T):
            break
        if n_list[i] == m_list[j]:
            if S[i] != T[j]:
                print(-1)
                return 0
        if n_list[i] > m_list[j]:
            j += 1
        elif n_list[i] < m_list[j]:
            i += 1
        else:
            i += 1
            j += 1
    print(key)

AGC028A()
import math
n, k = map(int, input().split())

for i in range(1, k+1):
    c = 1
    for j in range(i):
        c *= n - k + 1 - j
    for l in range(i-1):
        c *= k - 1 - l
    c /= math.factorial(i)
    c /= math.factorial(i - 1)
    print(int(c)%(10**9+7))

### FIXED CODE ###

import math
n, k = map(int, input().split())
 
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
 
for i in range(1, k+1):
    if i <= n - k + 1:
        c = 1
        c *= comb(n-k+1, i)
        c *= comb(k-1, i-1)
        print(c%(10**9+7))
    else:
        print(0)
A,B,C,D,E,F=map(int,input().split())

water=[]
for i in range(31):
    for j in range(30):
        if (A*i+B*j)*100<=F:
            water.append((A*i+B*j)*100)
sugar=[]
for i in range(501):
    for j in range(500):
        if C*i+D*j<=F//2:
            sugar.append(C*i+D*j)

ans_sum=A*100
ans_sugar=0
ans_rate=0
for i in water:
    for j in sugar:
        if i==0:
            continue
        if i+j<=F and ans_rate<j/i<=E/100:
            ans_sum=i+j
            ans_sugar=j
            ans_rate=j/i

print(ans_sum,ans_sugar)

### FIXED CODE ###

n,a=map(int,open(0));print(n**2-a)
# coding: utf-8
# Your code here!

N, M = (int(i) for i in input().split()) 
AB=[list(map(int,input().split())) for _ in range(N)]
# print(AB)
AB.sort()
# print(AB)

money = 0
for a, b in AB:

    # print(M) 
    if M==0:
        break
    elif b < M:
        # print(a*xb)
        money += a*b
        M -= b
    elif b >= M:
        # print(M)
        money += M*a
        M = 0
    # print(M, money)
print(money)
        

### FIXED CODE ###

a, b= (int(i) for i in input().split()) 
c, d = (int(i) for i in input().split()) 
print(((a-c)*(b-d)))
from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
p = list()
i = 3
while True:
  if g % i == 0:
    b = True
    for j in p:
      if i % j == 0:
        b = False
        break
    if b == True:
      p.append(i)
  i += 2
  if i > g/2:
    break
if g % 2 == 0:
  p.append(2)
for j in p:
  print(len(j)+1)


### FIXED CODE ###

from fractions import gcd

a, b = map(int, input().split())
g = gcd(a, b)

ans = 1

if g % 2 == 0:
  ans += 1
while g % 2 == 0:
  g /= 2

i = 3
while i * i <= g:
  if g % i == 0:
    ans += 1
  while g % i == 0:
    g /= i
  i += 2

if g != 1:
  ans += 1

print(ans)
N,M=map(int,input())

ans=(1900M+100(N-M))*2^M
print(ans)

### FIXED CODE ###

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

ans=(1900*M+100*(N-M))*(2**M)
print(ans)
a,b = map(int,input().split)
h,w = map(int,input().split)
print(a*b -a*w-b*h+h*w)


### FIXED CODE ###

H,W = map(int,input().split())
h,w = map(int,input().split())
print((H-h)*(W-w))
n = input()

a = int(n / 2)
b = n % 2

c = a + b

print(c)


### FIXED CODE ###

n = int(input())

a = int(n / 2)
b = n % 2

c = a + b

print(c/n)
D,G = map(int,input().split(' '))
l = [list(map(int,input().split())) for i in range(D)]

ans = 10**8
for i in range(2**D):
    score = 0
    tmp = 0
    n_list = []
    for j in range(D):
        if (i >> j & 1):
            k = l[j]
            score += (j+1)*100*k[0]+k[1]
            tmp += k[0]
        else:
            n_list.append([j+1]+l[j])
    e_flag = False
    for ii in n_list[::-1]:#[1or2or..,times,bonus]
        for jj in range(ii[1]-1):
            if score<G:
                score += ii[0]*100
                tmp += 1
            else:
                e_flag = True
                break
        if e_flag:
            break
    if score<G:
        continue
    ans = min(ans,tmp)
print(ans)

### FIXED CODE ###

r = int(input())
if r < 1200:
    ans = 'ABC'
elif r<2800:
    ans = 'ARC'
else:
    ans = 'AGC'
print(ans)
import math

a, b, h, m = map(int, input().split())

#c = (h/6 - m/360)*math.pi
c = 11.0/360.0*(60*h+m)*pi
x = math.sqrt(a * a + b * b - 2 * a * b * math.cos(c))
print(x)

#double c = (h/6 - m/360)*pi;
#x = sqrt(a * a + b * b - 2 * a * b * cos(c));
#cout << fixed << setprecision(15) << x << endl;


### FIXED CODE ###

import math

a, b, h, m = map(int, input().split())

#c = (h/6 - m/360)*math.pi
c = 11.0/360.0*(60*h+m)*math.pi
x = math.sqrt(a * a + b * b - 2 * a * b * math.cos(c))
print(x)

#double c = (h/6 - m/360)*pi;
#x = sqrt(a * a + b * b - 2 * a * b * cos(c));
#cout << fixed << setprecision(15) << x << endl;
import sys
sys.setrecursionlimit(10**9)
input = lambda:sys.stdin.readline().rstrip()

def Warshall_Floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d
############################
n, m, l = map(int, input().split())
f_inf = float('inf')
dist = [[f_inf]*n for _ in range(n)]
for i in range(m): dist[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    if c > l:
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c

dist = Warshall_Floyd(dist)

dist2 = [[f_inf]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if dist[i][j] <= l:
            dist2[i][j] = 1

dist2 = Warshall_Floyd(dist2)

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    ans = dist2[s-1][t-1]
    if dist2[s-1][t-1] == f_inf:
        print(-1)
    else:
        print(ans-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, L = map(int, input().split())
    dist = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if C > L:
            continue
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    e = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dist[i][j] <= L:
                e[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                e[i][j] = min(e[i][j], e[i][k] + e[k][j])


    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if e[s][t] == float('inf'):
            print(-1)
            continue
        ans = e[s][t]
        print(ans-1)


if __name__ == "__main__":
    main()
s = input()
r = ['SUN','MON','TUE','WED','THU','FRI','SAT']

for i in len(r):
  if s == r[i]:
    print(7-i)

### FIXED CODE ###

s = input()
r = ['SUN','MON','TUE','WED','THU','FRI','SAT']

for i in range(len(r)):
  if s == r[i]:
    print(7-i)
a,b=map(int,input().split())
if b==1:
    print(0)
elif a<b:
    x=(b-1)//(a-1)
    if (b-1)%(a-1)==0:
        print(x)
     else:
        print(x+1)
else:
    print(1)

### FIXED CODE ###

a,b=map(int,input().split())
if b==1:
    print(0)
elif a<b:
    x=(b-1)//(a-1)
    if (b-1)%(a-1)==0:
        print(x)
    else:
        print(x+1)
else:
    print(1)
n,m=map(int,input().split())
lst=[]
for i in range(m):
  p,y=map(int,input().split())
  lst.append([i,p,y])
lst.sort(lambda x:(x[1],x[2]))
j=1
Lst=[]
for i in range(m):
  if lst[i][1]==lst[min(m-1,i+1)][1]:
    s=str(lst[i][1])
    t=str(j)
    u=s.zfill(6)+t.zfill(6)
    j+=1
    Lst.append([lst[i][0],u])
  else:
    s=str(lst[i][1])
    t=str(j)
    u=s.zfill(6)+t.zfill(6)
    j-=j-1
    Lst.append([lst[i][0],u])
Lst.sort(lambda x:x[0])
for k in range(m):
  print(Lst[k][1])
  


### FIXED CODE ###

n,m=map(int,input().split())
lst=[]
for i in range(m):
  p,y=map(int,input().split())
  lst.append([i,p,y])
lst.sort(key=lambda x:(x[1],x[2]))
j=1
Lst=[]
for i in range(m):
  if lst[i][1]==lst[min(m-1,i+1)][1]:
    s=str(lst[i][1])
    t=str(j)
    u=s.zfill(6)+t.zfill(6)
    j+=1
    Lst.append([lst[i][0],u])
  else:
    s=str(lst[i][1])
    t=str(j)
    u=s.zfill(6)+t.zfill(6)
    j-=j-1
    Lst.append([lst[i][0],u])
Lst.sort(key=lambda x:x[0])
for k in range(m):
  print(Lst[k][1])
def main():
    s = input().rstrip()
    k = int(input().rstrip())

    if s[0] != '1':
        print(s[0])
        return

    cnt = 0
    for a in s:
        if a == '1':
            cnt += 1
        else:
            break

    if k < cnt:
        print(1)
    else:
        print(s[cnt])
    
    
main()


### FIXED CODE ###

def main():
    s = input().rstrip()
    k = int(input().rstrip())

    if s[0] != '1':
        print(s[0])
        return

    cnt = 0
    for a in s:
        if a == '1':
            cnt += 1
        else:
            break

    if k <= cnt:
        print(1)
    else:
        print(s[cnt])
    
    
main()
import numpy as np
N,M = map(int,input().split())
R = [[] for _ in range(M)]
ans = np.zeros(N,dtype=int)
ans[0] = 1
queue = [1]
for _ in range(M):
    i,j = map(int,input().split())
    R[i-1].append(j)
    R[j-1].append(i)
    
def bfs(queue):
    if queue==[]:
        return
    i = queue[0]
    for j in R[i-1]:
        if ans[j-1]!=0:
            continue
        else:
            ans[j-1]=i
            queue.append(j)
    queue.pop(0)
    bfs(queue)
bfs(queue)
if len(ans[ans==0])>0:
    print('No')
else:
    print('Yes')
    for i in range(1,N):
        print(ans[i])

### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
R = [[] for _ in range(N)]
ans = np.zeros(N,dtype=int)
ans[0] = 1
queue = [1]
for _ in range(M):
    i,j = map(int,input().split())
    R[i-1].append(j)
    R[j-1].append(i)
    
def bfs(que):
    if que==[]:
        return
    i = que[0]
    for j in R[i-1]:
        if ans[j-1]==0:
            ans[j-1]=i
            que.append(j)
    que.pop(0)
    bfs(que)
    
bfs(queue)
print('Yes')
for i in range(1,N):
    print(ans[i])
Indata = [int(i) for i in input().split()]
W,H,x,y,r = int(i) for i in Indata
x_right = x+r
x_left = x-r
y_on = y+r
y_under = y-r

if x_right>W || x_left<0 || y_on>H || y_under<0:
    print("No")
else:
    print("Yes")


### FIXED CODE ###

Indata = [int(i) for i in input().split()]
W,H,x,y,r = [int(i) for i in Indata]
x_right = x+r
x_left = x-r
y_on = y+r
y_under = y-r

if x_right>W or x_left<0 or y_on>H or y_under<0:
    print("No")
else:
    print("Yes")
from math import floor, ceil

S = input()
a = S[:floor(len(S)/2)]

n = 0
for i in range(floor(len(S)/2)):
    if not a[i] == S[-(i+1)]:
        n += 1
    
print(n)

### FIXED CODE ###

from math import floor, ceil

S = input()
a = S[:floor(len(S)/2)]

n = 0
for i in range(floor(len(S)/2)):
    if not a[i] == S[-(i+1)]:
        n += 1
    
print(n)
data = input()
data_list = data.split()
if ((data_list[0]*data_list[1])%2 == 0):
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a,b = map(int, input().split())
if (a * b) % 2 == 0:
  print('Even')
else:
  print('Odd')
Imp = input()
A = Imp[0]
B = Imp[1]
re = 0
if A % 3 == 0:    
    re = 1
if B % 3 == 0:
    re = 1
if (A+B) % 3 == 0:
        re = 1
        
if re ==1:
    print("Possible")
else:
    print("Impossible")


### FIXED CODE ###

Imp = list(map(int, input().split()))
A = Imp[0]
B = Imp[1]
re = 0
if A % 3 == 0:    
    re = 1
if B % 3 == 0:
    re = 1
if (A+B) % 3 == 0:
        re = 1
        
if re ==1:
    print("Possible")
else:
    print("Impossible")
import math
N,K = map(int,input().split())
if N > 4000:
  raise IndexError
cnt = 0
for n in range(1,N+1):
    if K/n <= 1:
        x = 0
    elif math.log(K/n)%math.log(2)<=0.00001:
        x = (math.log(K)-math.log(n))//math.log(2)
    else:
        x = (math.log(K)-math.log(n))//math.log(2)+1
    cnt += (0.5)**x
 
print(cnt/N)

### FIXED CODE ###

import math
N,K = map(int,input().split())
cnt = 0
for n in range(1,N+1):
    x = 0
    while n*(2**x) < K:
        x += 1
    cnt += (0.5)**x

print(cnt/N)
N, Y = map(int, input().split())
for i1 in range(0,N)
	for i2 in range(0,N-i1)
  		if N-i1<0
    		break
  		for i3 in range(0,N-i1-i2)
        	if N-i1-i2<0
          		break
    		if Y==10000*i1+5000*i2+1000*i3:
        		print(i1,i2,i3)
          		break
        else:
    else:
else:

### FIXED CODE ###

N, Y = map(int, input().split())
 
for x in range(N+1):
  for y in range(N-x+1):
    z = N - x - y
    if 10000 * x + 5000 * y + 1000 * z == Y:
      print(x,y,z)
      exit()
print(-1,-1,-1)
a, b, c, d, e, k = [int(input()) for in range(6)]
print("Yey!" if (e-a)<=k else ":(")

### FIXED CODE ###

a, b, c, d, e, k = [int(input()) for i in range(6)]
print("Yay!" if (e-a)<=k else ":(")
N = list(map(int,input().split()))
M = 10**9 + 7
red = N[0] - N[1]
x=1
for i in range(1,N[1]+1):
    x *= (red+2-i)*(N[1]-i)//(i*(i-1))
    print(x%M)

### FIXED CODE ###

# -*- coding:utf-8 -*-

def cmb(n, r):
    if n == 0 or r == 0:
        return 1
    if n < r:
        return 0
    a = b = 1
    r = min(n-r,r)
    for i in range(1, r + 1):
        a *= i
    for i in range(n-r+1,n+1):
        b *= i
    return b//a

N = list(map(int,input().split()))
M = 10**9 + 7
red = N[0]-N[1]
for i in range(1,N[1]+1):
    x = cmb(red + 1, i) * cmb(N[1] - 1,i-1)
    print(x%M)
import sys
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
cnt = [[0 for _ in range(15)] for _ in range(15)]
ans = 0
for _ in range(n):
	a = input()
	x, y = 0, 0
	if "." in a:
		i = len(a)-1
		while a[i] != ".":
			i -= 1
			x, y = x-1, y-1
		b = int(a[:i] + a[i+1:])
	else:
		b = int(a)
	while b%2 == 0:
		x += 1
		b //= 2
	while b%5 == 0:
		y += 1
		b //= 5
	#print(x, y)
	x, y = x+9, y+9
	for i in range(18-x, 15):
		for j in range(18-y, 15):
			ans += cnt[i][j]
	cnt[x][y] += 1
print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
cnt = [[0 for _ in range(20)] for _ in range(20)]
ans = 0
for _ in range(n):
	a = input()
	x, y = 0, 0
	if "." in a:
		i = len(a)-1
		while a[i] != ".":
			i -= 1
			x, y = x-1, y-1
		b = int(a[:i] + a[i+1:])
	else:
		b = int(a)
	#print(b)
	while b%2 == 0 and x < 9:
		x += 1
		b //= 2
	while b%5 == 0 and y < 9:
		y += 1
		b //= 5
	#print(x, y)
	x, y = x+9, y+9
	for i in range(18-x, 20):
		for j in range(18-y, 20):
			ans += cnt[i][j]
	cnt[x][y] += 1
print(ans)
x = input()
a = input()
y = int(x)
b = int(a)
 
 
 
 
if y < b:
  print(0)
else:
  print(10)

### FIXED CODE ###

i = list(map(int, input().split()))
if i[0] < i[1]:
  print("0")
else:
  print("10")
str = input()
data = "".split(str)
n1 = int(data[0])
n2 = int(data[1])
if (n1 >9 or n2 > 9):
    print(-1)
else:
    print(n1*n2)

### FIXED CODE ###

str = input()
data = str.split()
n1 = int(data[0])
n2 = int(data[1])
if (n1 >9 or n2 > 9):
    print(-1)
else:
    print(n1*n2)
input = input().split(" ")
if int(input[0]) > 10:
  c = 10 - int(input[0])
  r = 100 * int(c)
  print(r)
else:
  print(input[1]

### FIXED CODE ###

input = input().split(" ")
if int(input[0]) < 10:
  c = 10 - int(input[0])
  r = 100 * int(c)
  res = int(input[1]) + int(r)
  print(res)
elif int(input[0]) >= 10:
  print(input[1])
n=int(input())
a=list(map(int,input().split()))
count=1
if 0 in a:
  print(0)
  exit(0)
for i in a:
    count*=i
	if count>10**18:
    	print(-1)
        exit(0)
print(count)


### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
ans = 1
if 0 in lis:
  print(0)
  exit()
for num in lis:
  ans *= num
  if ans > 10 ** 18:
    print(-1)
    exit()
print(ans)
N = int(input())
s = input()

while s.count('000'):
    s = s.replace('000', '00')
ss = s.split('00')

A = []
for si in ss:
    num = 0
    ai = []
    for c in si:
        if c == '1':
            num += 1
        else:
            if num > 0:
                ai.append(num)
                num = 0

    if num > 0:
        ai.append(num)

    A.append(ai)

ans = 0
for ai in A:
    if ai[0] < ai[-1]:
        ai = ai[::-1]

    flg = True
    for i, aa in enumerate(ai):
        if i == len(ai) - 1:
            break

        if flg == True:
            ans += aa
            flg = False
        else:
            ans += aa - 1
            if aa == 1:
                flg = True

print(ans)


### FIXED CODE ###

N = int(input())
s = input()

# 「連続する1の数」のリストに変換する
s = s[s.find('1'):] # 先頭の'0'を取り除く
while s.count('000'):
    s = s.replace('000', '00')
cs = list(map(len, s.split('0')))

# dp[i]: i番目の「連続する1」への各処理（操作に使わない／左の１つだけ使う／右の１つを残して使う／全て使う）
#        に対して、現時点での操作回数の最大値
dp = [[-float('inf')] * 4 for i in range(len(cs))]
dp[0][0] = 0
for i in range(1, len(cs)):
    if cs[i] == 0:
        dp[i][3] = max(dp[i - 1])
        continue

    # 使わない
    dp[i][0] = max(dp[i - 1])
    # 全て使う
    dp[i][3] = max(dp[i - 1][0] + max(cs[i - 1], cs[i]), \
                   dp[i - 1][1] + max(cs[i - 1] - 1, cs[i]), \
                   dp[i - 1][2] + cs[i], \
                   dp[i - 1][3])
    if cs[i] >= 2:
        # 左の１つだけ使う
        dp[i][1] = max(dp[i - 1][0] + cs[i - 1], \
                       dp[i - 1][1] + cs[i - 1] - 1, \
                       dp[i - 1][2] + 1, \
                       dp[i - 1][3])
        # 右の１つを残して使う
        dp[i][2] = max(dp[i - 1][0] + max(cs[i - 1], cs[i] - 1), \
                       dp[i - 1][1] + max(cs[i - 1] - 1, cs[i] - 1), \
                       dp[i - 1][2] + cs[i] - 1, \
                       dp[i - 1][3])

print(max(dp[-1]))
N = int(input())
c = list(map(str, input().split()))

a=0
b=0

a = c.count("R")

for i in range(N):
    if S[i] == 'R':
        a -= 1
    else:
        b += 1

    now = max(a,b)
    ans = min(ans, now)

print(ans)

### FIXED CODE ###

N = int(input())
c = list(input())

a=0
b=0

a = c.count("R")
ans = c.count("R")
for i in range(N):
    if c[i] == "R":
        a -= 1
    else:
        b += 1

    now = max(a,b)
    ans = min(ans, now)

print(ans)
H1, M1, H2, M2, K = map(int, input().split())

startTime = (H1*60)+M1
endTime = (H2*60)+M2
time = endTime - startTime
posTime = time - k
if (posTime < 0):
  print(0)
else:
  print(posTime)

### FIXED CODE ###

H1, M1, H2, M2, K = map(int, input().split())

startTime = (H1*60)+M1
endTime = (H2*60)+M2
time = endTime - startTime
posTime = time - K
if (posTime < 0):
  print(0)
else:
  print(posTime)
def main():
    import sys
    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(100001)]
    mark=[0]*N
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A-1].append(B-1)
        dic[B-1].append(A-1)
    
    def dfs(idx):
        if mark[idx]:
            return
        mark[idx]=1
        for a in dic[idx]:
            dfs(a)

    i=0
    count=0
    while True:
        if not mark[i]:
            count+=1
            dfs(i)
        i+=1
        if i==N:
            break
    
    print(count-1)
main()

### FIXED CODE ###

def main():
    import sys
    from collections import deque

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(100001)]
    sys.setrecursionlimit(100001)
    mark=[0]*N
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A-1].append(B-1)
        dic[B-1].append(A-1)


    i=0
    count=0
    while True:
        if not mark[i]:
            count+=1
            d=deque()
            d.appendleft(i)
            while d:
                a=d.popleft()
                mark[a]=1
                for j in dic[a]:
                    if mark[j]:
                        continue
                    
                    d.appendleft(j)
        i+=1
        if i==N:
            break
    
    print(count-1)
main()