Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def main():

	N = int(input())
	#N, K = map(int, input().split(" "))

	xy = []
	for _ in range(N):
		x, y = map(int, input().split(" "))
		xy.append((x,y))

	xy.sort()
	gess = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val
		p = x - xm
		q = y - ym
		if (p,q) in gess:
			gess[(p, q)] += 1
		else:
			gess[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess, key=gess.get)
	nai = gess[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[0],-x[1]))
	gess2 = {}
	xm = 0
	ym = 0

	#print(xy)

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val
		p = x - xm
		q = y - ym
		if (p,q) in gess2:
			gess2[(p, q)] += 1
		else:
			gess2[(p, q)] = 1
		xm = x
		ym = y

	#print(gess2)

	p, q = max(gess2, key=gess2.get)
	nai2 = gess2[(p,q)]

	tmp = max(nai, nai2)

	print(N-tmp)



if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N = int(input())
	xy = []
	for i in range(N):
		x, y = map(int, input().split(" "))
		xy.append((x, y))
		
	if N == 1:
		print(1)
		sys.exit()
		
	re = {}
	for i, val in enumerate(xy):
		x, y = val
		for j, vol in enumerate(xy):
			if i == j:
				continue
			nx, ny = vol
			p = nx - x
			q = ny -y
			if (p, q) in re:
				re[(p, q)] += 1
			else:
				re[(p, q)] = 1
				
	ans = N - max(re.values())
	
	print(ans)
	
	
if __name__ == "__main__":
	main()
n,m = map(int,input())
while n <= m:
  if m%n == 0:
    print(m%n)
    break
  n += 1

### FIXED CODE ###

n,m = map(int, input().split())
if n*n <= m:
  k = n
  while k*k <= m:
    if m%k == 0:
      print(m//k)
      exit()
    k += 1
else:
  n = m//n

k = n
while True:
  if m%k == 0:
    print(k)
    exit()
  k -= 1
n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i-N), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i - 100), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)
S = int(input())

W = int(input())

if S >= W/2:
  print("unsafe")
  
else:
  print("safe")

### FIXED CODE ###

s, w = map(int, input().split())

if w >= s:
  print("unsafe")
  
else:
  print("safe")
s = input()
ans = 0
if s[0]=="1":
    ans = += 1
if s[1]=="1":
    ans = += 1
if s[2]=="1"
    ans += 1
print(ans)

### FIXED CODE ###

s = input()
ans = 0
if s[0]=="1":
    ans += 1
    
if s[1]=="1":
    ans += 1

if s[2]=="1":
    ans += 1

print(ans)
import sys
import numpy as np
from heapq import heappop, heappush

# Dijikstra
def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)])
    grid = np.pad(grid, 1)
    # atcoderではnp.pad() のargにconstant_valuesを指定できない
    q = []
    heappush(q, (0, 1, 1))
    visited = set()
    cost = np.full((H + 1, W + 1), np.inf)
    cost[1][1] = 0
    while q:
        c, i, j = heappop(q)
        if (i, j) in visited:
            continue
        visited.add((i, j))
        cost[i][j] = c
        if i == H and j == W:
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                heappush(q, (c + 1, y, x))
    

    if cost[H][W] != np.inf:
        ans = int(np.sum(grid == '.') - (cost[H][W] + 1))
    else:
        ans = -1

    print(ans)  
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
from heapq import heappop, heappush


def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='U')
    grid = np.pad(grid, 1, mode='constant')

    can_go = False
    i = j = 1 # start
    c = 0     # real cost
    h = max(H - i, W - j) # goalまでの推定cost 
    s = c + h # score
    q = [] # open list
    heappush(q, (s, c, i, j))
    visited = set() # closed list
    # parent = [[None * (W + 1)] for _ in range(H+1)]

    while q:
        s, c, i, j = heappop(q)
        visited.add((i, j))
        if c == s: 
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                visited.add((y, x))
                h = max(H - y, W - x)
                s = h + c + 1
                heappush(q, (s, c+1, y, x))
 
    if can_go:
        ans = (grid == '.').sum() - (c + 1)
    else:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
a,b = map(int,input().split())

print(lcm(a,b))


### FIXED CODE ###

def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y % x, x)

def lcm(x, y):
    return (x * y) // gcd(x, y)
a,b = map(int,input().split())

print(lcm(a,b))
a=input()
b=input()
count=0
for str_i in range (len(a)):
  if a[str_i] != b[str_i]:
	count+=1
print(count)

### FIXED CODE ###

S=input()  
T=input()
num = 0
for i in range(len(S)):
	if S[i] != T[i]:
		num= num+1
print(num)
a = sorted(int(i) for i in input().split()) 
print((a[1] - a[0]+1) // 2 + a[2] - a[1] + (a[1] - a[0]) % 2)

### FIXED CODE ###

a = input()
if a in ["abc","acb","bac","bca","cab","cba"]: #== ("abc" or "acb" or "bac" or "bca" or "cab" or "cba"):
  print("Yes")
else:
  print("No")
cnt = 0
num = '1'
    s = input()
    for i in range(len(s)):
        if s[i] == num:
            cnt += 1
        if num == '1':
            num = '0'
        else:
            num = '1'
    print(min(int(len(s)-cnt),cnt))

### FIXED CODE ###

cnt = 0
num = '1'
s = input()
for i in range(len(s)):
    if s[i] == num:
        cnt += 1
    if num == '1':
        num = '0'
    else:
        num = '1'
print(min(int(len(s)-cnt),cnt))
n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]
for i in range(n):
    a.append(a[i] + A[i])
for i in range(m):
    b.append(b[i] + B[i])
ans = 0
j = m
for i in range(n + 1):
    if a[0] > k:
        break
    while b[j] > k - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)


### FIXED CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]
for i in range(n):
    a.append(a[i] + A[i])
for i in range(m):
    b.append(b[i] + B[i])
ans = 0
j = m
for i in range(n + 1):
    if a[i] > k:
        break
    while b[j] > k - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
AB, BC = map( int, input().split() )
print( AB * BC // 2 )

### FIXED CODE ###

AB, BC, CA = map( int, input().split() )
print( ( AB * BC ) // 2 )
n = int(input())
xy = [list(map(int,input().split())) for _ in range(n-1)]
xy_1d = list(itertools.chain.from_iterable(xy))
c = collections.Counter(xy_1d)
cc = c.most_common()
num_max = cc[0][0]
color = cc[0][1]
color_list = [i+1 for i in range(color)]
length = len(xy)
l = [color]
for i in range(length):
    if i < color:
        l.append(color_list[i])
    elif i >= color:
        num = i - int(length/color)*color
        l.append(color_list[num])
for j in l:
    print(j)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
 
N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
    V[a].add(b)
    V[b].add(a)
#print(V)
maxc = 0
for v in V:
    maxc = max(maxc,len(v))
#print(maxc)
CE = {}
for e in E:
    CE[e] = 0
#print(CE)
 
def dfs(u,t,c):
    if t > 0:
        CE[(min(u,t),max(u,t))] = c
    cc = c+1
    if cc > maxc:
        cc = 1
    for v in V[u]:
        if CE[(min(u,v),max(u,v))] == 0:
            dfs(v,u,cc)
            cc += 1
            if cc > maxc:
                cc = 1
dfs(1,0,1)
print(maxc)
for e in E:
    print(CE[e])
n=(input())
rem=str(n)

if int(n[-1:]) in str(2) or str(4) or str(7) or str(9):
  print('hon')
if int(n[-1:]) in str(0) or str(1) or str(6) or str(8):
  print('bon')
if int(n[-1:]) == str(3):
  print('pon')
  


### FIXED CODE ###

n = input()
if n[-1:] == str(2) or  n[-1:] ==  str(4)  or  n[-1:] ==  str(5) or  n[-1:] == str(7) or  n[-1:] == str(9):
  print('hon')
if (n[-1:]) == str(0) or  n[-1:] == str(1) or  n[-1:] == str(6) or  n[-1:] == str(8):
  
  print('pon')
if (n[-1:]) == str(3):
  print('bon')
N = int(input())
A = list(map(int,input().split()))
if all(v%2==1 or v%3==0 or v%5==0):
    print("APPROVED")
else:
    print("DENIED")


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
if all(v%2==1 or v%3==0 or v%5==0 for v in A):
    print("APPROVED")
else:
    print("DENIED")
N = int(input())

P2 = list(range(2,30001,2))
P3 = list(range(3,30001,6))
for i in range(1,N+1):
  if (N-i*3)%2==0 and 3*i<=15000 and (N-3*i)<=5000:
    x = 3*i
    y = (N-i*3)
    break
if N==5 or N>6:
  ans = P2[:x]+P3[:y]
elif N==3:
  ans = [2,5,63]
elif N==4:
  ans = [2,5,20,63]
elif N==6:
  ans = [2,3,4,185,7,9]
print(*ans)

### FIXED CODE ###

N = int(input())

P2 = list(range(2,30001,2))
P3 = list(range(3,30001,6))
for i in range(1,5002):
  if (N-i*3)%2==0 and 0<(N-3*i)<=5000:
    x = 3*i
    y = (N-i*3)
    break
if N==5 or N>6:
  ans = P2[:x]+P3[:y]
elif N==3:
  ans = [2,5,63]
elif N==4:
  ans = [2,5,20,63]
elif N==6:
  ans = [2,3,4,185,7,9]
if N==19999:
  ans = P2[:14997]+P3[:5000]+[19,425]
print(*ans)
print(x**3)\n

### FIXED CODE ###

x = int(input())
print (x ** 3)
w,h,n=map(int,input().split())
xya = [list(map(int, input().split())) for _ in range(n)]
w1=w
h1=h
for i in range(n):
    if xya[i][2]==1:w1=w-int(xya[i][0])
    elif xya[i][2]==2:w1-=(w-int(xya[i][0])
    elif xya[i][2]==3:h1=h-int(xya[i][1])
    elif xya[i][2]==4:h1-=(h-int(xya)[i][1])
    else:pass
if w1>0 and h1>0:print(w1*h1)
else:print(0)


### FIXED CODE ###

w,h,n=map(int,input().split())
xya = [list(map(int, input().split())) for _ in range(n)]
wl,wr,hu,ht=0,w,0,h
for i in range(n):
    if xya[i][2]==1:
        wl=max(wl,int(xya[i][0]))
    elif xya[i][2]==2:
        wr=min(wr,int(xya[i][0]))
    elif xya[i][2]==3:
        hu=max(hu,int(xya[i][1]))
    elif xya[i][2]==4:
        ht=min(ht,int(xya[i][1]))
    else:pass
if wl>wr or hu>ht:print(0)
else:print((wr-wl)*(ht-hu))
s,t = input(),input()
x,r,nx,p = s*2,0,{},'.'

for i,c in enumerate(s):
	if nx.get((c,x[j])) is None:
		nx[('.',c)] = i+1
	else:
		continue
	for j in range(i+1,len(x)):
		if nx.get((c,x[j])) is None:
			nx[(c,x[j])] = j-i

for c in t:
	n = nx.get((p,c))
	if n is None:
		print(-1)
		exit()
	r,p = r+n,c
print(r)

### FIXED CODE ###

from bisect import bisect

s,t = input(),input()
n,x,nx,r = len(s),s+s,{},0

for i,c in enumerate(x):
	if nx.get(c) is None:
		nx[c] = []
	nx[c].append(i+1)

for c in t:
	l = nx.get(c)
	if l is None:
		print(-1)
		exit()
	r += l[bisect(l,r%n)]-r%n
print(r)
from sys import stdin

import itertools

import copy

import collections






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

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

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

ans = -10000000000

if K <= N:
    for i in range(N):
        count = 0
        tmp_point = 0
        nv = i
        while count < K:
            nvv = P[nv]
            nvv -= 1
            tmp_point += C[nvv]
            count += 1
            nv = nvv
            ans = max(ans, tmp_point)
    print(ans)
else:
    loop = [0]*N
    for i in range(N):
        count = 0
        check = [False]*N
        tmp_point = 0
        nv = i
        while True:
            nvv = P[nv]
            nvv -= 1
            if check[nvv] == True:
                break
            check[nvv] = True
            tmp_point += C[nvv]
            count += 1
            nv = nvv
            ans = max(ans, tmp_point)
        loop[i] = [tmp_point, count, i]
    loop.sort(reverse=True)
    max_volue =  loop[0][0]
    #print(loop)
    if 0 <= max_volue:
        new_ans = -10000000
        for value, counter, key in loop:
            if value != max_volue:
                break
            shou = K//counter
            amari = K%counter
            tmp_ans = value*shou
            new_ans = max(new_ans, tmp_ans)
            count = 0
            nv = key
            while count < amari:
                nvv = P[nv]
                nvv -= 1
                tmp_ans += C[nvv]
                count += 1
                nv = nvv
                new_ans = max(new_ans, tmp_ans)
        print(new_ans)
        
    else:
        print(max(max(loop),ans))
        
            
    
    



    
    

    











### FIXED CODE ###

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

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

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

ans = -10000000000

if K <= N:
    for i in range(N):
        count = 0
        tmp_point = 0
        nv = i
        while count < K:
            nvv = P[nv]
            nvv -= 1
            tmp_point += C[nvv]
            count += 1
            nv = nvv
            ans = max(ans, tmp_point)
    print(ans)
else:
    loop = [0]*N
    for i in range(N):
        count = 0
        check = [False]*N
        tmp_point = 0
        nv = i
        while True:
            nvv = P[nv]
            nvv -= 1
            if check[nvv] == True:
                break
            check[nvv] = True
            tmp_point += C[nvv]
            count += 1
            nv = nvv
            ans = max(ans, tmp_point)
        loop[i] = [tmp_point, count, i]
    loop.sort(reverse=True)
    #print(loop)
    new_ans = -10000000
    for value, counter, key in loop:
        if value < 0:
            break
        shou = K//counter-1
        amari = K%counter+counter
        tmp_ans = value*shou
        new_ans = max(new_ans, tmp_ans)
        count = 0
        nv = key
        while count < amari:
            nvv = P[nv]
            nvv -= 1
            tmp_ans += C[nvv]
            count += 1
            nv = nvv
            new_ans = max(new_ans, tmp_ans)

        
    print(max(loop[0][0], ans, new_ans))
# -*- coding: utf-8 -*-
"""
D - Various Sushi
https://atcoder.jp/contests/abc116/tasks/abc116_d

"""
import sys

from collections import Counter

def solve(N, K, sushi):
    sushi.sort(key=lambda x: x[1], reverse=True)
    pick = sushi[:K]
    rem = sushi[K:][::-1]
    all_type = set([t for t, d in sushi])
    pick_type = set([t for t, d in pick])

    cnt = Counter()
    for t, d in pick:
        cnt[t] += 1

    manzoku = sum([d for t, d in pick])
    ans = [manzoku + len(pick_type)**2]
    while pick_type != all_type:
        t, d = rem.pop()
        if t not in pick:
            pick_type.add(t)
            tt, dd = pick.pop()
            if cnt[tt] > 1:
                cnt[tt] -= 1
                manzoku = manzoku - dd + d
                ans.append(manzoku+ len(pick_type)**2)
    return max(ans)



def main(args):
    N, K = map(int, input().split())
    sushi = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, K, sushi)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
D - Various Sushi
https://atcoder.jp/contests/abc116/tasks/abc116_d

"""
import sys

from collections import Counter

def solve(N, K, sushi):
    sushi.sort(key=lambda x: x[1], reverse=True)
    pick = sushi[:K]            #  おいしさポイントの高い方からK個の寿司を選択
    pick_type = set([t for t, d in pick]) # 選択済の種類

    cnt = Counter()             #  各種類の寿司が何個ずつあるか覚えておく
    for t, d in pick:
        cnt[t] += 1

    rem = dict()                #  未選択の種類の寿司のうち、一番おいしさポイントが高い物
    for t, d in sushi:
        if t not in pick_type:
            rem[t] = max(rem.get(t, 0), d)
    res = sorted([[k, v] for k, v in rem.items()], key=lambda x: x[1]) # おいしさで昇順にソート(一番おいしい物が末尾)

    manzoku = sum([d for t, d in pick])
    ans = [manzoku + len(pick_type)**2] #  現在の選択でのスコア、ここから種類を1つずつ増加させていきスコアを計算する
    while len(pick_type) < K and pick and res:
        t, d = res.pop()
        pick_type.add(t)
        tt, dd = pick.pop()
        while cnt[tt] == 1 and pick:
            tt, dd = pick.pop()
        if cnt[tt] > 1:
            cnt[tt] -= 1
            manzoku = manzoku - dd + d
            ans.append(manzoku+ len(pick_type)**2)
    return max(ans)


def main(args):
    N, K = map(int, input().split())
    sushi = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, K, sushi)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
s=input()
s+='T'
x,y=map(int,input().split())
n=len(s)
f=0
d=0
xx=[]
yy=[]
for i in range(n):
    if s[i]=='F':
        f+=1
    else: #=='T'
        if f==0:
            0
        else:
            if d==0:
                xx.append(f)
                f=0
            else:
                yy.append(f)
                f=0
        d=1-d

if len(x)>0:
    x[0]=t
    x.remove(x[0])
    xx.append(abs(x-t))
else:
    xx.append(abs(x))
yy.append(abs(y))

#rint(xx,yy)
def judg(a):
    tot=sum(a)
    if tot%2==1:
        return False
    else:
        dp=[0]*(tot+1)
        for i in a:
            dp[i]=1
            for j in range(tot+1):
                if dp[j]==1 and j+i<=tot:
                    dp[j+i]=1
        if dp[int(tot/2)]==1:
            return True
        else:
            return False
if judg(xx) and judg(yy):
    ans='Yes'
else:
    ans='No'
print(ans)
    


### FIXED CODE ###

s=input()
s+='T'
x,y=map(int,input().split())
n=len(s)
f=0
d=0
xx=[]
yy=[]
for i in range(n):
    if s[i]=='F':
        f+=1
    else: #=='T'
        if f==0:
            0
        else:
            if d==0:
                xx.append(f)
                f=0
            else:
                yy.append(f)
                f=0
        d=1-d
#print(xx,yy)
def judg(a,b):
    if len(a)==0 and b==0:
        return True
    else:
        dp=set()
        pdp=set()
        for i in a:
            pdp=dp
            if len(pdp)==0:
                pdp.add(i)
                pdp.add(-i)
            else:
                dp=set()
                for j in pdp:
                    dp.add(j-i)
                    dp.add(j+i)
                    #print(dp)
        if b in dp:
            return True
        else:
            return False
    
if s[0]!='T' and len(xx)>0:
    t=xx[0]
    xx.remove(xx[0])
else:
    t=0



if judg(xx,x-t) and judg(yy,y):
    ans='Yes'
else:
    ans='No'
print(ans)
n=int(input())
mod=10**9+7
exlcusion=2*pow(9,n,mod)-pow(8,n,mod)
total=pow(10,n,mod)
ans=total-exclusion%mod
print(total)

### FIXED CODE ###

n=int(input())
if n<2:

    print(0)
else:
 
    mod=10**9+7
    exclusion=2*pow(9,n,mod)-pow(8,n,mod)
    total=pow(10,n,mod)
    ans=total-exclusion
    print(ans%mod)
s = input()
ans = []
c=0
for st in s:
    if st in ["A","T","C","G"]:
        c+=1
    else:
        ans.append(c)
        c=0
print(max(ans))


### FIXED CODE ###

s = input()+"E"
ans = []
c=0
for st in s:
    if st in ["A","T","C","G"]:
        c+=1
    else:
        ans.append(c)
        c=0
print(max(ans))
import math
n,m=map(int,input().split())
s=list(input())
t=list(input())
num=(n*m)//math.gcd(n,m)
str1=["A"]*num
ans=num
numn=num//n
numm=num//m
for i in range(n):
    str1[i*(numn)]=s[i]
for i in range(m):
    str2=str1[i*numm]
    if str2!="A" and str2!=t[i]:
        ans=-1
        break
print(ans)


### FIXED CODE ###

import math
n,m=map(int,input().split())
s=list(input())
t=list(input())
num=math.gcd(n,m)
ans=(n*m)//num
numn=n//num
numm=m//num
for i in range(num):
    if s[i*numn]!=t[i*numm]:
        ans=-1
        break
print(ans)
n = int(input())

for A in range(n):
    A = list(map(int, input().split()))
        if A % 3 == 0 or A % 5 == 0:
            print("APPROVED")
        else:
            print("DENIED")

### FIXED CODE ###

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

if a==b and a!=c:
    print("Yes")
elif a==c and a!=b:
    print("Yes")
elif b==c and b!=a:
    print("Yes")
else:
    print("No")
K = int(input())
A,B = map(int,input().split())
if A == B:
	if K//A == 0:
        print('OK')
	else:
        print('NG')
else:
	if K//A == K//B:
		print('NG')
	else:
		print('OK')


### FIXED CODE ###

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

for i in range(1000):
  if K*i >= A and K*i <= B:
    print('OK')
    break
else:
  print('NG')
res = 0
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007


    N,M = map(int, input().split())
    g = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int, input().split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)

    visited = [0]*N

    def dfs(node):
      	global res
        visited[node]=1
        if all(visited):
            res += 1
            return
        for n_node in g[node]:
                if not visited[n_node]:
                    dfs(n_node)
                    visited[n_node] = 0
    dfs(0)
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    n,m = map(int, input().split())
    edge = [list(map(int, input().split())) for _ in range(m)]
    res = []
    visited = [0]*n

    def dfs(node):
        visited[node-1]=1
        if sum(visited)==n:
            res.append(1)
            return
        for x,y in edge:
            if x == node:
                if not visited[y-1]:
                    dfs(y)
                    visited[y-1] = 0
            if y == node:
                if not visited[x-1]:
                    dfs(x)
                    visited[x-1] = 0

    for a,b in edge:
        if a==1:
            dfs(a)
            print(len(res))
            exit()

if __name__ == '__main__':
    main()