Harryxun/stf_run huggingface dataset:
def main():
    height, width = map(int, input().split(" "))
    grids = ["." * (width + 2)]
    for _ in range(height):
        tmp = input()
        grids.append("." + tmp + ".")
    grids.append("." * (width + 2))
    is_possible = True
    for i in range(1, width + 1):
        for j in range(1, height + 1):
            if grids[i][j] == "#":
                if not(grids[i + 1][j] == "#" or grids[i - 1][j] == "#" or grids[i][j + 1] == "#" or grids[i][j - 1] == "#"):
                    is_possible = False
    if is_possible:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    height, width = map(int, input().split(" "))
    grids = ["." * (width + 2)]
    for _ in range(height):
        grids.append("." + input() + ".")
    grids.append("." * (width + 2))
    is_possible = True
    for i in range(1, height + 1):
        for j in range(1, width + 1):
            if grids[i][j] == "#":
                if not (grids[i + 1][j] == "#" or grids[i - 1][j] == "#" or grids[i][j + 1] == "#" or grids[i][j - 1] == "#"):
                    is_possible = False
    if is_possible:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()
S = input()
l = sorted(list(set(S)))

ans ="None"
number = [96]
for i in range(len(S)):
  if ord(l[i]) ==  number[-1] + 1:
    number.append(ord(l[i]))
  else:
    ans = chr(number[-1]+1)
    break

print(ans)

### FIXED CODE ###

S = input()
l = sorted(list(set(S)))

ans = ""
for i in range(len(l)):
  if ord(l[i]) !=  97 + i:
    ans = chr(97+i)
    break
  elif i == 25 and l[i] == "z":
    ans = "None"

if ans != "":
 print(ans)
else:
  print(chr(ord(l[-1])+1))
s = input()
li = input().split()
ans = 1
t = 0
li2 = []
while True:
    for i in li:
        if int(i) % 2 == 0:
            li2.append(int(i)/2)
        else:
            t = 1
    if t == 1:
        break
    else:
        ans += 1
        li = li2

print(ans)

### FIXED CODE ###

li = list(input())
ans = 0
for i in li:
    if int(i) == 1:
        ans += 1

print(ans)
s = input()
k = int(input())

li = []

count = 1
tmp = s[0]

for i in range(1,len(s)):
    if s[i] == tmp:
        count += 1
    else:
        li.append((s[i-1],count))
        count = 1
    tmp = s[i]
if count != 1:
    li.append((s[-1],count))
    
if len(li) == 1:
    print(li[0][1] * k // 2)
elif li[0][0] == li[-1][0] and k >= 2:
    li2 = [(li[0][0],li[0][1]+li[-1][1])]
    for i in range(1,len(li)-1):
        li2.append(li[i])
    ans = 0
    for i in li2:
        ans += i[1] // 2
    ans *= k - 1
    for i in li:
        ans += i[1] // 2
    print(ans)
else:
    ans = 0
    for i in li:
        ans += i[1] // 2
    ans *= k
    print(ans)


### FIXED CODE ###

s = input()
k = int(input())

li = []

count = 1
tmp = s[0]

if len(s) == 1:
    print(k//2)
    exit()

for i in range(1,len(s)):
    if s[i] == tmp:
        count += 1
    else:
        li.append((s[i-1],count))
        count = 1
    tmp = s[i]
if count != 1:
    li.append((s[-1],count))

if len(li) == 1:
    print(li[0][1] * k // 2)
elif li[0][0] == li[-1][0] and k >= 2:
    li2 = [(li[0][0],li[0][1]+li[-1][1])]
    for i in range(1,len(li)-1):
        li2.append(li[i])
    ans = 0
    for i in li2:
        ans += i[1] // 2
    ans *= k - 1
    for i in li:
        ans += i[1] // 2
    print(ans)
else:
    ans = 0
    for i in li:
        ans += i[1] // 2
    ans *= k
    print(ans)
def f(a,n,ans1,p1,p2,flag):
    if p1>p2:
        return ans1
    if flag&1==0:
        return max(f(a,n,ans1+a[p1],p1+1,p2,flag+1),
                   f(a,n,ans1+a[p2],p1,p2-1,flag+1))
    return min(f(a,n,ans1,p1+1,p2,flag+1),f(a,n,ans1,p1,p2-1,flag+1))
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
p1=0
p2=n-1
first=f(a,n,0,p1,p2,2)
print(first-(s-first))


### FIXED CODE ###

def f(a,i,j,dp):
    if dp[i][j]==-1:
        if i>j:
            return 0

        dp[i][j]=max(a[i]+min(f(a,i+2,j,dp),f(a,i+1,j-1,dp)),
                                a[j]+min(f(a,i+1,j-1,dp),f(a,i,j-2,dp)))
    return dp[i][j]
        
n=int(input())
dp=[[-1 for i in range(n)] for j in range(n)]
a=list(map(int,input().split()))
for i in range(n):
    dp[i][i]=a[i]

for i in range(n-1):
    dp[i][i+1]=max(a[i],a[i+1])

s1=f(a,0,n-1,dp)

print(s1-sum(a)+s1)
n = int(input())
s = input()
if s[:int(n/2)] == s[int(n/2):n] :
    print("Yes")
else
    print("No")

### FIXED CODE ###

n = int(input())
s = input()
if s[:int(n/2)] == s[int(n/2):n] :
    print("Yes")
else:
    print("No")
from heapq import heappush, heappop
N, *L = map(int, open('0').read().split())
dic = [[] for i in range(N)]
ans = [-1]*N
cnt = [0]*N
hq = []
for a,b in zip(*[iter(L[:2*(N-1)])]*2):
  a -= 1
  b -= 1
  dic[a] += [b]
  dic[b] += [a]
  cnt[a] += 1
  cnt[b] += 1
C = L[2*(N-1):]
C.sort()
for i in range(N):
  heappush(hq,(cnt[i],i))
arg = 0
m = 0
while True:
  c, i = heappop(hq)
  if ans[i]!=-1:
    continue
  m += C[arg]*cnt[i]
  ans[i] = C[arg]
  arg += 1
  if arg==N:
    break
  for v in dic[i]:
    cnt[v] -= 1
    heappush(hq,(cnt[v],v))
print(m)
print(*ans)

### FIXED CODE ###

from heapq import heappush, heappop
N, *L = map(int, open(0).read().split())
dic = [[] for i in range(N)]
ans = [-1]*N
cnt = [0]*N
hq = []
for a,b in zip(*[iter(L[:2*(N-1)])]*2):
  a -= 1
  b -= 1
  dic[a] += [b]
  dic[b] += [a]
  cnt[a] += 1
  cnt[b] += 1
C = L[2*(N-1):]
C.sort()
for i in range(N):
  heappush(hq,(cnt[i],i))
arg = 0
m = 0
while True:
  c, i = heappop(hq)
  if ans[i]!=-1:
    continue
  m += C[arg]*cnt[i]
  ans[i] = C[arg]
  arg += 1
  if arg==N:
    break
  for v in dic[i]:
    cnt[v] -= 1
    heappush(hq,(cnt[v],v))
print(m)
print(*ans)
S, T = input().split("\n")

cnt = []
for i in range(len(S)-len(T)+1):
	
	mismatch = 0
	for j in range(len(T)):
		if S[i+j] != T[j]:
			mismatch += 1
	cnt.append(mismatch)
	
print(min(cnt))

			


### FIXED CODE ###

S = input()
T = input()
  
cnt = []
for i in range(len(S)-len(T)+1):
	mismatch = 0
	for j in range(len(T)):
		if S[i+j] != T[j]:
			mismatch += 1
	cnt.append(mismatch)
	
print(min(cnt))
s, c = map(int, ip().split())
if s >= c//2:
	print(c//2)
else:
	print(s + (c-s*2)//4)

### FIXED CODE ###

s, c = input().split()
s = int(s); c = int(c)
if s >= c//2:
	print(c//2)
else:
	print(s+(c-s*2)//4)
# Vicfred
# https://atcoder.jp/contests/abc042/tasks/abc042_a
# sorting
import algorithm, strutils, sequtils

var line = stdin.readLine.split.map(parseInt)
line.sort
if line == [5, 5, 7]:
  echo "YES"
else:
  echo "NO"



### FIXED CODE ###

# Vicfred
# https://atcoder.jp/contests/abc042/tasks/abc042_a
# implementation, sorting
ins = list(map(int, input().split()))
ins.sort()

if ins == [5, 5, 7]:
    print("YES")
else:
    print("NO")
A, B = list(map(int, input()))
if A<9 and B<9:
    print('Yay!')
else:
    print(':(')


### FIXED CODE ###

A, B = list(map(int, input().split()))
if A<9 and B<9:
    print('Yay!')
else:
    print(':(')
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

cnt = 0
t = 1
for i in a:
    t = a[t-1]
    cnt += 1
    if t == 2:
        print(cnt)
        exit(1)
print(-1)

### FIXED CODE ###

import sys

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

cnt = 0
t = 1
for i in a:
    t = a[t-1]
    cnt += 1
    if t == 2:
        print(cnt)
        sys.exit()
print("-1")
inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = [inputs[1]]

for day in conditions.keys():
  conditions[day].sort(reverse=True)

ans = 0
candidates = []
for reversed_day in range(1, m+1):
  if reversed_day in conditions.keys():
    candidates.append(conditions[reversed_day])

  cand_len = len(candidates)
  if cand_len == 0:
    continue
  maxval, maxidx = 0, 0
  for i in range(cand_len):
    if candidates[i][0] > maxval:
      maxval = candidates[i][0]
      maxidx = i
  ans += candidates[maxidx].pop(0)
print(ans)



### FIXED CODE ###


import collections
import heapq

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = collections.deque([])
for i in range(n):
  conditions.append([int(x) for x in input().split()])

conditions = sorted(conditions)

cnt, ans = 0, 0
candidates = []
for reversed_day in range(1, m + 1):
  while cnt < len(conditions) and conditions[cnt][0] <= reversed_day:
    heapq.heappush(candidates, -conditions[cnt][1])
    cnt += 1

  if len(candidates) == 0:
    continue
  ans -= heapq.heappop(candidates)

print(ans)
a, b, k = map(int, input().split())
ans = []
for i in range(1, min(a, b)):
    if a % i == 0 and b % i == 0:
        ans.append(i)
print(ans[-k])

### FIXED CODE ###

a, b, k = map(int, input().split())
ans = []
for i in range(1, 101):
    if a % i == 0 and b % i == 0:
        ans.append(i)
print(ans[-k])
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
ans_count = 0

while:
  count = len(np.where(a % 2 == 1)[0])
  if count > 0:
    break
  a = a / 2
  ans_count += 1
print(ans_count)

### FIXED CODE ###

num_str = input()

print(sum([1 for a in num_str if a == '1']))
n,m=map(int,input().split())
s=[]
for i in range(1,int(m**2)+1):
    if m%i==0 and i<n:
        s.append(i)
        if m/i<n:
           s.append(m/i)
print(max(s))

### FIXED CODE ###

n, m = list(map(int,input().split()))
def solve():
    for i in range(m//n, 0, -1):
        if m % i == 0:
            if m//i>= n:
                print(i)
                break
solve()
def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.append(n)
    # divisors.sort()
    return divisors

n=int(input())
l=[]
# print(make_divisors(n))
for i in make_divisors(n):
    k=i-1
    if n//k==n%k:
        # print(k+1,n//k,n%k)
        l.append(k)
# print(l)
print(sum(l))



### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.append(n)
    # divisors.sort()
    return divisors

n=int(input())
l=[]
# print(make_divisors(n))
md=make_divisors(n)
if 1 in md:
    md.remove(1)
for i in md:
    k=i-1
    if n//k==n%k:
        # print(k+1,n//k,n%k)
        l.append(k)
# print(l)
print(sum(l))
a, b, c = map(int, input().split())
if a + b + c < 22:
    print('win')
else:
    ptint('bust')

### FIXED CODE ###

a, b, c = map(int, input().split())
if a + b + c < 22:
    print('win')
else:
    print('bust')
H = int(input())

cnt = H
B = [H]
if H == 1:
    print('0')
else:
    for i in range(100000000000):
    cnt = cnt//2
    B.append(cnt)
    if cnt == 1:
        break
    C =[1]
    for i in range(1,1001):
        C.append(C[i-1]*2)
    ans= 0
    for i in range(len(B)):
        ans +=C[i]
    print(ans)

### FIXED CODE ###

H = int(input())
cnt = H
ans = 0
B = [H]

if H == 1:
    ans == 'NA'
else:
    for i in range(100000000000):
        cnt = cnt//2
        B.append(cnt)
        if cnt == 1:
            break

C =[1]
for i in range(1,1001):
    C.append(C[i-1]*2)

if ans == 'NA':
    print('0')
else:
    for i in range(len(B)):
        ans +=C[i]
print(ans)
a = input()
s = input()

print( s if a >3200 else: 'red')

### FIXED CODE ###

a = input()
s = input()

print(s if int(a) >= 3200 else 'red')
a,b,c=map(int,input().split())
d=[]
for i in range(a,b+1):
	d.append(i)
#print(d)
e=[]
if c<=b:
	for i in range(c):
		e.append(d[i])
		e.append(d[-i-1])
else:
	for i in d:
		print(i)
for i in sorted(set(e)):
	print(i)


### FIXED CODE ###

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

if b-a+1>2*c:
	x=[i for i in range(a,a+c)]
	y=[i for i in range(b-c+1,b+1)]
	e=x+y
else:
	e=[i for i in range(a,b+1)]
#print(e)
for i in e:
	print(i)
N = int(input())
XYH_list = [list(map(int, input().split())) for i in range(N)]

for i in range(1, 101):
    for j in range(1, 101):
        tmpH = 0
        tmpI = i
        tmpJ = j
        for k, xyh in enumerate(XYH_list):
            if k == 0:
                for l in range(1, 100000):
                    if xyh[2] == max(l - abs(xyh[0] - i) - abs(xyh[1] - j), 0):
                        tmpH = l
                        break
            if xyh[2] == max(tmpH - abs(xyh[0] - i) - abs(xyh[1] - j), 0):
                if k == N - 1:
                    ans = [str(tmpI), str(tmpJ), str(tmpH)]
                continue
            else:
                break
print(' '.join(ans))


### FIXED CODE ###

N = int(input())
XYH_list = [list(map(int, input().split())) for i in range(N)]
XYH_list = sorted(XYH_list, key=lambda x: x[2], reverse=True)

for xi in range(0, 101):
    for yi in range(0, 101):
        tmpH = 0
        for k in range(N):
            x,y,h = XYH_list[k]
            if k == 0:
                tmpH =h + abs(x - xi) + abs(y - yi)
            if h == max((tmpH - abs(x - xi) - abs(y - yi)), 0):
                if k == N - 1:
                    ans = [str(xi), str(yi), str(tmpH)]
                continue
            else:
                break
print(' '.join(ans))
n = int(input())
s = list(input().split())
a=[]
w=[]
t=[]
r=[]

for i in range (n):
  if s[i] == "AC":
    a.append(s[i])
  elif s[i]== "WA":
    w.append(s[i])
  elif s[i]== "TLE":
    t.append(s[i])
  else:
    r.append(s[i])
  
print("AC x ",sum(a))
print("WA x ",sum(w))
print("TLE x ",sum(t))
print("RE x ",sum(r))
  

### FIXED CODE ###

n = int(input())
s = list(input() for i in range(n))
  
print("AC x ",s.count("AC"))
print("WA x ",s.count("WA"))
print("TLE x ",s.count("TLE"))
print("RE x ",s.count("RE"))
N,i=int(input ("enter the number of cars and car ))
X=N-i+1
Print(x)

### FIXED CODE ###

N,i=map(int,input().split( ))
count=0

while N>=i:
    count+=1
    N-=1


print(count)
import numpy as np
N, M = map(int, input().split())
 
G = np.zeros((N, M)) 
total_path_num = 0
not_reach_node = list(range(1, N))
node = 0
 
for i in range(M):
  a, b = map(int, input().split())
  G[a-1, b-1] += 1
  G[b-1, a-1] += 1
  
def search_path(G, not_reach_node, node):
  global total_path_num
  if len(not_reach_node) == 0:
    total_path_num += 1
    return total_path_num
  
  for x in np.where((G[node] == 1))[0]:
    try:
      if (x in not_reach_node):
        not_reach_node_copy = not_reach_node.copy()
        not_reach_node_copy.remove(x)
        search_path(G, not_reach_node_copy, x)
    except:
      pass
        
search_path(G, not_reach_node, node)      	
 
print(total_path_num)

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
 
G = np.zeros((N, N)) 
total_path_num = 0
not_reach_node = list(range(1, N))
node = 0
 
for i in range(M):
  a, b = map(int, input().split())
  G[a-1, b-1] += 1
  G[b-1, a-1] += 1
  
def search_path(G, not_reach_node, node):
  global total_path_num
  if len(not_reach_node) == 0:
    total_path_num += 1
    return total_path_num
  
  for x in np.where((G[node] == 1))[0]:
    if (x in not_reach_node):
      not_reach_node_copy = not_reach_node.copy()
      not_reach_node_copy.remove(x)
      search_path(G, not_reach_node_copy, x)

search_path(G, not_reach_node, node)      	
 
print(total_path_num)
a,b = map(int,input().split())
dum1 = min(a,b)
dum2 = max(a,b)
ans = ""
for i in range(dum2):
  ans += str(dum1)
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
if n == 7:
    if s == "keyence":
        print("YES")
    else:
        print("NO")
else:
    if s[n-7:n] == "keyence" or (s[0]+s[n-6:n]) == "keyence" or (s[0:2]+s[n-5:n]) == "keyence" or (s[0:3]+s[n-4:n]) == "keyence" or (s[0:4]+s[n-3:n]) == "keyence" or (s[0:5]+s[n-2:n]) == "keyence" or  (s[0:6]+s[n-1:n]) == "keyence"  or (s[0:7]) == "keyence":
        print("YES")
    else:
        print("NO")
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

sum = sum(c) + sum(b) - c[a[n-1]-1]

print(sum)


### FIXED CODE ###

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

last = -1

sum = sum(b) 

for i in range(n):
    if last == a[i]-1:
        sum += c[last-1]
    last = a[i]
print(sum)
import sys
from math import ceil, floor, comb
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n,m = map(int, input().split())
    print((comb(n,2)) + (comb(m,2)))
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from math import ceil, floor, factorial
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def comb(n, r):
    if n-r < 0:
        return 0
    return factorial(n) // (factorial(n - r) * factorial(r))


def main():
    n,m = map(int, input().split())
    print((comb(n,2)) + (comb(m,2)))
    return

if __name__ == '__main__':
    main()
time =input()
h=0
h = int(time/(60*60))
m=int(time/60-h*60)
s=int(time-h*60*60-m*60)
print(str(h)+":"+str(m)+":"+str(s))javascript:void(0)


### FIXED CODE ###

time =int(input())
h = int(time/(60*60))
m=int(time/60-h*60)
s=int(time-h*60*60-m*60)
print(str(h)+":"+str(m)+":"+str(s))
a,b,c =map(int,input().split())
for num in range(1,b):
	if a*num%b==c :	
		print("YES");sys.exit(0);
print("NO")


### FIXED CODE ###

a,b,c =input().split()
a=int(a)
b=int(b)
c=int(c)
f=0
for num in range(1,b):
	d=a*num
	d%=b
	if d==c :
		f=1
if f:	
	print("YES")
else:
	print("NO")
x = [int(i) for i in input().split()]
x.pop(0)

M = max(x)
m = min(x)
s = sum(x)

print("{0} {1} {2}".format(m,M,s))

### FIXED CODE ###

input()
x = [int(i) for i in input().split()]

M = max(x)
m = min(x)
s = sum(x)

print("{0} {1} {2}".format(m,M,s))
import numpy as np 
n = int(input())
e = [[int(i) for i in input().split()] for i in range(2)] 
e3 = np.array(e)
print(np.sort((e3[0] - e3[1]))[::-1][0] + np.sort((e3[0] - e3[1]))[::-1][1])


### FIXED CODE ###

import numpy as np 
n = int(input())
if n  < 2:
    print(0)
    exit()
e = [[int(i) for i in input().split()] for i in range(2)]
e3 = np.array(e)
a = np.sort((e3[0] - e3[1]))
print(a[a>0].sum())
x, y = map(int, input().split())
print(max([x - y, 0])

### FIXED CODE ###

x, y = map(int, input().split())
print(max([x - y, 0]))
N, T = list(map(int, input().split()))

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

if N == 1:
    print(T)
    exit(T)

ans = 0
buff = 0
for i in range(N):
    if T > t[i]:
        buff = t[i]

    elif T <= t[i]:
        if buff + T > t[i]:
            ans += t[i]
        elif buff + T <= t[i]:
            ans += T + buff
        buff = 0

ans += T
print(ans)



### FIXED CODE ###

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

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

if N == 1:
    print(T)
    exit()

# t.pop(0)
ans = 0
buff = 0
for i in range(N):
    if i != 0:
        if t[i] - t[i-1] < T:
            ans += t[i] - t[i-1]
        else:
            ans += T

ans += T
print(ans)
N,Q = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  adj[a].append(b)

from collections import defaultdict
counter = defaultdict(int)
for _ in range(Q):
  p,x = map(int,input().split())
  p -= 1
  counter[p] += x

weight = [-1] * N
def dfs(node, wei):
  weight[node] = wei

  for nei in adj[node]:
    if weight[nei] == -1:
      dfs(nei, wei+counter[nei])

dfs(0, counter[0])
print(" ".join(map(str,weight)))

### FIXED CODE ###

from collections import deque
N,Q = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  adj[u].append(v)
  adj[v].append(u)

scores = [0] * N
for _ in range(Q):
  u,p = map(int,input().split())
  u -= 1
  scores[u] += p

res = [0] * N
visited = [False] * N
q = deque([(scores[0], 0)])
while q:
  s,n = q.popleft()
  res[n] = s
  visited[n] = True

  for nei in adj[n]:
    if not visited[nei]:
      q.append((s+scores[nei], nei))

print(" ".join(map(str, res)))
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())
al=[ [] for i in range(N+1) ]	#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#リバース隣接リスト
I=[ 0 for i in range(N+1) ] #入次数
O=[ 0 for i in range(N+1) ] #出次数
edge=[] #辺の集合
I[0]=None

for _ in range(M):
    s,t=map(int, sys.stdin.readline().split())
    al[s].append(t)
    rev_al[t].append(s)
    I[t]+=1
    O[s]+=1
    edge.append((s,t))

#トポロジカルソート
L=[]
q=deque()
q.append(1) #startは常に1

while q:
    fro=q.popleft()
    L.append(fro)
    for to in al[fro]:
        I[to]-=1
        if I[to]==0:
            q.append(to)

if len(L)!=N:
    prin

#頂点毎の到達する確立
P=[ 0 for i in range(N+1) ]   #確率
P[1]=1

for x in L:
    if O[x]!=0:
        p=float(1)/O[x]
        for to in al[x]:
            P[to]+=P[x]*p
        
#頂点毎の期待値
E=[ 0 for i in range(N+1) ]   #期待値

for x in L[::-1]:
    for to in rev_al[x]:
        p=float(1)/O[to]
        E[to]+=(E[x]+1)*p
#消す辺
ans=E[1]
for del_s,del_t in edge:
    if O[del_s]-1==0:
        continue
    new_E=float(E[del_s]*O[del_s]-(E[del_t]+1))/(O[del_s]-1)
    #print "del_s,del_t,new_E, :: ",del_s,del_t,new_E,E,E[1]+(new_E-E[del_s])*P[del_s]
    if new_E<E[del_s]:
        ans=min(ans,E[1]-(E[del_s]-new_E)*P[del_s])

print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())
al=[ [] for i in range(N+1) ]	#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#リバース隣接リスト
O=[ 0 for i in range(N+1) ] #出次数
edge=[] #辺の集合

for _ in range(M):
    s,t=map(int, sys.stdin.readline().split())
    al[s].append(t)
    rev_al[t].append(s)
    #I[t]+=1
    O[s]+=1
    edge.append((s,t))


#頂点毎の到達する確立
P=[ 0 for i in range(N+1) ]   #確率
P[1]=1
 
for x in range(1,N+1):
    if O[x]!=0:
        p=float(1)/O[x]
        for to in al[x]:
            P[to]+=P[x]*p
        
#頂点毎の期待値
E=[ 0 for i in range(N+1) ]   #期待値

for x in range(N,0,-1):
    for to in rev_al[x]:
        p=float(1)/O[to]
        E[to]+=(E[x]+1)*p


#消す辺
ans=E[1]
for del_s,del_t in edge:
    if O[del_s]-1==0:
        continue
    new_E=float(E[del_s]*O[del_s]-(E[del_t]+1))/(O[del_s]-1)
    #print "del_s,del_t,new_E, :: ",del_s,del_t,new_E,E,E[1]+(new_E-E[del_s])*P[del_s]
    if new_E<E[del_s]:
        ans=min(ans,E[1]-(E[del_s]-new_E)*P[del_s])

print ans
from collections import deque
import numpy as np

def main():
    n,m = map(int,input().split())
    arr = np.zeros([n,n])
    for _ in range(m):
        a, b = map(int,input().split())
        arr[a-1][b-1] = 1
        arr[b-1][a-1] = 1
    q = deque()
    q.append(0)
    path = {i:0 for i in range(2, n+1)}
    while q:
        pos = q.popleft()
        for i in range(1, n):
            if arr[pos][i] == 1:
                q.append(i)
                if path[i+1] == 0:
                    path[i+1] = pos + 1
        if len(q) == 0:
            break
        flag = True
        for i in path:
            if path[i] == 0:
                flag = False
        if flag:
            break
    print('Yes')
    for i in path:
        print(path[i])

if __name__=='__main__':
    main()


### FIXED CODE ###

from collections import deque

def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.popleft()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.append(next)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()
n=int(input())
print(n*(n-1)//2)

### FIXED CODE ###

s=input()
t=input()
ans=0
for i in range(3):
	if s[i]==t[i]:
		ans+=1
print(ans)