Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]

c = [i for i in range(2, n + 1)]
b = []
for x in itertools.permutations(c):
  b.append([1] + list(x))
  
cnt = 0
for x in b:
  exist = True
  for i in range(n-1):
    if not sorted(x[i:i+2]) in a:
      exist = False
      break
  if exist:
    cnt += 1

print(cnt)

### FIXED CODE ###

import itertools

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]

c = [i for i in range(2, n + 1)]
b = []
for x in itertools.permutations(c):
  b.append([1] + list(x))
  
cnt = 0
for x in b:
  exist = True
  for i in range(n-1):
    if not sorted(x[i:i+2]) in a:
      exist = False
      break
  if exist:
    cnt += 1

print(cnt)
import numpy as np
def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    h = np.array(h)
    cost = np.empty(n)
    cost[0] = 0
    cost[1] = abs(h[1] - h[0])
    for i in range(2, n):
        j = min(i, k)
        cost[i] = np.min(cost[i-j:i-1] + np.abs(h[i-j:i-1] - h[i]))
    print(int(cost[-1]))
main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    cost = [0 for _ in range(n)]
    cost[0] = 0
    cost[1] = abs(h[1] - h[0])
    for i in range(2, n):
        cost[i] = min((cost[i-1-j] + abs(h[i]-h[i-1-j]) for j in range(min(i, k))))
    print(cost[-1])
main()
H, W = map(int,input().split())
map = [input() for i in range(H)]

def drow(i,j, map = map):
  if j > 0 and map[i][j-1] == ".":
    return "No"
  if j < W-1 and map[i][j+1] == ".":
    return "No"
  if i > 0 and map[i-1][j] == ".":
    return "No"
  if i < H -1 and map[i+1][j] == ".":
    return "No"
  return "Yes"

for i in range(H):
  for j in range(W):
    if map[i][j] == "#":
      ans = drow(i,j)
      if ans == "No":
        break
print(ans)

### FIXED CODE ###

H, W = map(int,input().split())
map = [input() for i in range(H)]

def drow(i,j, map = map):
  if j > 0 and map[i][j-1] == "#":
    return "Yes"
  if j < W-1 and map[i][j+1] == "#":
    return "Yes"
  if i > 0 and map[i-1][j] == "#":
    return "Yes"
  if i < H -1 and map[i+1][j] == "#":
    return "Yes"
  return "No"

ans = "Yes"
for i in range(H):
  for j in range(W):
    if map[i][j] == "#":
      ans = drow(i,j)
      if ans == "No":
        print(ans)
        exit()
print(ans)
D = int(input())
 
if D = 25:
  print("Chrismas")
elif D = 24:
  print("Chrismas Eve")
elif D = 23:
  print("Chrismas Eve Eve")
elif D = 22:
  print("Chrismas Eve Eve Eve")

### FIXED CODE ###

D = int(input())
 
if D == 25:
  print("Christmas")
elif D == 24:
  print("Christmas Eve")
elif D == 23:
  print("Christmas Eve Eve")
elif D == 22:
  print("Christmas Eve Eve Eve")
MOD = 10**9 + 7
N, K = map(int,input().split())

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

    G[a].append(b)
    G[b].append(a)

# 頂点nowを根とする部分木の色の塗り方 (parが親の時)
#   ただしnowはすでに塗られているとする
def dfs(now, par):
    if K < len(G[now]): return 0

    res = 1

    if par == -1:
        colors = K-1
        for i in range(len(G[now])):
            res *= colors-i
            res %= MOD
    else:
        colors = K-2
        for i in range(len(G[now])-1):
            res *= colors-i
            res %= MOD

    for c in G[now]:
        if c == par: continue
        
        res *= dfs(c, now)
        res %= MOD
    
    return res

print(K * dfs(0,-1) % MOD)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

MOD = 10**9 + 7
N, K = map(int,input().split())

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

    G[a].append(b)
    G[b].append(a)

# 頂点nowを根とする部分木の色の塗り方 (parが親の時)
#   ただしnowはすでに塗られているとする
def dfs(now, par):
    if K < len(G[now]): return 0

    res = 1

    if par == -1:
        colors = K-1
        for i in range(len(G[now])):
            res *= colors-i
            res %= MOD
    else:
        colors = K-2
        for i in range(len(G[now])-1):
            res *= colors-i
            res %= MOD

    for c in G[now]:
        if c == par: continue
        
        res *= dfs(c, now)
        res %= MOD
    
    return res

print(K * dfs(0,-1) % MOD)
c = input()
al = "abcdefghijklmnopqrstuvwxz"
print(al[al.index(c)+1])

### FIXED CODE ###

c = input()
al = "abcdefghijklmnopqrstuvwxyz"
print(al[al.index(c)+1])
n,m = map(int,input().split())
S = list(map(int,input().split()))
ac = 0
wa = 0
for j in range(n):
  for i in range(m):
    if S[i] == "AC":
      ac += 1
      i += 1
      j += 1
    else:
      wa += 1
      i += 1
print(ac)
print(wa)

### FIXED CODE ###

N,M = map(int,input().split())
AC = 0
penalty = 0
AC_list = [0]*N
WA_list = [0]*N

for i in range(M):
  p,s = map(str,input().split())
  p = int(p)-1
  if s == "AC" and AC_list[p] == 0:
    AC += 1
    AC_list[p] = 1
    penalty += WA_list[p]
  elif s == "WA":
    WA_list[p] += 1
  if AC == N:
    break
print(AC,penalty)
from itertools import groupby
S = input()
A = [len(list(it)) for s, it in groupby(S)]
B = [[0]*(n1-1)+[(n1+1)//2+n2//2]+[n1//2+(n2+1)//2]+[0]*(n2-1)
     for n1, n2 in zip(A[::2], A[1::2])]
print(*sum(B, []))from itertools import groupby
S = input()
A = [len(list(it)) for s, it in groupby(S)]
for n1, n2 in zip(A[::2], A[1::2]):
    print(*([0]*(n1-1)+[(n1+1)//2+n2//2]+[n1//2+(n2+1)//2]+[0]*(n2-1)), end=" ")

### FIXED CODE ###

from itertools import groupby
S = input()
A = [len(list(it)) for s, it in groupby(S)]
for n1, n2 in zip(A[::2], A[1::2]):
    print(*([0]*(n1-1)+[(n1+1)//2+n2//2]+[n1//2+(n2+1)//2]+[0]*(n2-1)), end=" ")
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    from collections import deque as d
    N, M = map(int, readline().split())
    m = map(int, read().split())
    AB = zip(m, m)
    graph = [[] for _ in range(N + 1)]
    for a, b in AB:
        graph[a].append(b)
        graph[b].append(a)
    que = [1]
    stack = [1]
    ans = [0]*(N+1)
    while que:
        x = d.popleft(que)
        for i in graph[x]:
            if ans[x] == 0:
                ans[x] = x
            stack.append(i)
    for a in ans[2:]:
        if a == 0:
            print('No')
            break
    else:
        print('Yes')
        print('\n'.join(map(str, ans[2:])

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    from collections import deque as d
    N, M = map(int, readline().split())
    m = map(int, read().split())
    AB = zip(m, m)
    graph = [[] for _ in range(N + 1)]
    for a, b in AB:
        graph[a].append(b)
        graph[b].append(a)
    que = d([1])
    ans = [0]*(N+1)
    while que:
        x = d.popleft(que)
        for i in graph[x]:
            if ans[i] != 0:
                continue
            ans[i] = x
            que.append(i)
    for a in ans[2:]:
        if a == 0:
            print('No')
            break
    else:
        print('Yes')
        print('\n'.join(map(str, ans[2:])))

    return

if __name__ == '__main__':
    main()
# -*- coding: utf-8 -*-


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

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


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def main():
    s = input()
    k = int(input())
    one_count = 0

    for si in s:
        if si == '1':
            one_count += 1
        else:
            break

    if s[0] == '1':
        if k == 1:
            print(s[0])
        elif one_count >= k:
            print(1)
        elif one_count < k:
            print(s[one_count])
        else:
            print(s[1])
    else:
        print(s[0])


if __name__ == '__main__':
    main()
mport numpy as np
n = int(input())
a = [int(input()) for x in range(n)]
print(np.amax(abs(np.subtract.outer(a, a))))


### FIXED CODE ###

# ABC102B

import numpy as np
n = int(input())
a = [int(x) for x in input().split()]
print(np.amax(abs(np.subtract.outer(a, a))))
N, P = [int(i) for i in input().strip().split()]
dic={}

for i in range(2,int(P**(1/2))+1):
    num = 0
    while P%i == 0:
        num = num +1
        P = P/i
    dic[i] = num
    
for i in dic:
    for j in dic:
        if i < j:
            if j%i == 0:
                del dic[j]
                
ans = 1
for i in dic:
    if N == 1:
        ans = P
        break
    elif dic[i] != 0:
        ans = ans*(i**(dic[i]//N))
print(ans)

### FIXED CODE ###

N, P = [int(i) for i in input().strip().split()]
dic={}
ans = 1

if N == 1:
    print(P)
    quit()
elif P == 1:
    print(1)
    quit()
    
for i in range(2,int(P**(1/2))+1):
    num = 0
    while P%i == 0:
        num = num +1
        P = int(P/i)
    dic[i] = num//N
    ans = ans*(i**(dic[i]))

print(ans)
#import math

input = raw_input
n = int(input())

as = list(map(int, input().split(" ")))
sa = sum(as)
#half_sa= sa // 2 if sa % 2 == 0 else (sa // 2) + 1
half_sa = sa // 2

cur_val = 0
for i, a in enumerate(as):
    cur_val += a
    if half_sa <= cur_val:
        over_i = i # made
        break

cur_val2 = cur_val
cur_val1 = cur_val - a

#print(cur_val1, half_sa, cur_val2)
diff1 = half_sa - cur_val1
diff2 = cur_val2 - half_sa

val_a = cur_val1
val_b = sa - val_a

val_c = cur_val2
val_d = sa - val_c

out = min(val_b-val_a, val_c - val_d)

#if diff1 <= diff2:
#    #half_sa = int(math.floor(half_sa))
#    out = diff1
#else:
#    out = diff2
print(out)

### FIXED CODE ###

#import math

#input = raw_input
n = int(input())

As = list(map(int, input().split(" ")))
sA = sum(As)
#half_sA= sA // 2 if sA % 2 == 0 else (sA // 2) + 1
half_sA = sA // 2

cur_val = 0
for i, a in enumerate(As):
    cur_val += a
    if half_sA <= cur_val:
        over_i = i # made
        break

cur_val2 = cur_val
cur_val1 = cur_val - a

#print(cur_val1, half_sA, cur_val2)
diff1 = half_sA - cur_val1
diff2 = cur_val2 - half_sA

val_a = cur_val1
val_b = sA - val_a

val_c = cur_val2
val_d = sA - val_c

out = min( abs(val_b-val_a), abs(val_c-val_d) )

#if diff1 <= diff2:
#    #half_sA = int(math.floor(half_sA))
#    out = diff1
#else:
#    out = diff2
print(out)
import sys


def calc_area_size(a):
    return int(3 * (a ** 2))


if __name__ == '__main__':
    r = sys.argv[1]
    print(calc_area_size(r))

### FIXED CODE ###

from sys import stdin

print(int(3 * (int(stdin.readline().rstrip()) ** 2)))
import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.func(self.a[i], x)
            i += i & (-i)

    def get(self, i):
        s = self.one
        i += 1
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    que = [[i, list(map(int, input().split())), 0] for i in range(q)]
    que.sort(key=lambda x: x[1][1])
    
    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            que[j][2] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    que.sort()
    for i in que:
        print(i[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, a):
        self.n = len(a)
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.a[i] + x
            i += i & (-i)

    def get(self, i):
        s = 0
        i += 1
        while i != 0:
            s = s + self.a[i]
            i -= i & (-i)
        return s


def inmin(x):
    return int(x)-1


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(inmin, input().split()))
    que = [[i, list(map(inmin, input().split()))] for i in range(q)]
    que.sort(key=lambda x: x[1][1])
    ans = [0] * q

    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            ans[que[j][0]] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    print(*ans)
n = int(input())
A = list(map(int, input().split()))

maxV = (10 ** 6 + 1)

sieve = [i for i in range(maxV)]
p = 2

while p*p < maxV:
    if sieve[p] == p:
        for q in range(p*2, maxV, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

from math import gcd

g = 0
primes = set()
for a in A:
    g = gcd(g, A)

    v = a
    while a > 1:
        prime = sieve[a]
        if prime in primes:
            print('')
        primes.add(prime)
        a = a // prime


if g > 1:
    print('not coprime')

for a in A:
    while a > 1:
        prime = sieve[a]
        if prime in primes:
            print('pairwise coprime')
            exit()
        primes.add(prime)
        a = a // prime

print('setwise coprime')

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))

maxV = (10 ** 6 + 1)

sieve = [i for i in range(maxV)]
p = 2

while p*p < maxV:
    if sieve[p] == p:
        for q in range(p*2, maxV, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

from math import gcd

g = 0
primes = set()
for a in A:
    g = gcd(g, a)

    v = a


if g > 1:
    print('not coprime')
    exit()

for a in A:
    temp_prime = set()
    while a > 1:
        prime = sieve[a]
        temp_prime.add(prime)
        a = a // prime

    for t in temp_prime:
        if t in primes:
            print('setwise coprime')
            exit()
        primes.add(t)

print('pairwise coprime')
a=int(input())
p=a%10
b=int(input())
q=b%10
c=int(input())
r=c%10
d=int(input())
s=d%10
e=int(input())
t=e%10
l=[a,b,c,d,e]
m=[p,q,r,s,t]
ans=0
minimum=min(list(set(m)-set([0])))
def func(n):
    if n%10==0:
        return n
    else:
        return (n//10)*10+10
for i in range(5):
    ans+=func(l[i])
ans=ans-10+minimum
print(ans)

### FIXED CODE ###

a=int(input())
p=a%10
b=int(input())
q=b%10
c=int(input())
r=c%10
d=int(input())
s=d%10
e=int(input())
t=e%10
l=[a,b,c,d,e]
m=[p,q,r,s,t]
ans=0
if set(m)==set([0]):
    minimum=10
else:
    minimum=min(list(set(m)-set([0])))
def func(n):
    if n%10==0:
        return n
    else:
        return (n//10)*10+10
for i in range(5):
    ans+=func(l[i])
ans=ans-10+minimum
print(ans)
a,b=map(int,input().split())
if a==b:
  print("draw")
elif a=1 or a>b
  print("Alice")
elif b=1:
  print("Bob")
else:
  print("Bob")

### FIXED CODE ###

a, b = map(int, input().split())
if a==b:
  ans = 'Draw'
elif a==1:
  ans = 'Alice'
elif b==1:
  ans = 'Bob'
elif a>b:
  ans = 'Alice'
else:
  ans = 'Bob'
print(ans)
X, Y = map(int, input().split(" "))


def num_combinations_mod(n, r, mod, num_max=10**6):
    # if this functions is called twice or more, init process should be placed before calling this function to
    # save time.
    f_mod, f_mod_inv = num_combinations_mod_init(num_max, mod)
    return f_mod[n] * (f_mod_inv[r] * f_mod_inv[n-r] % mod) % mod


def num_combinations_mod_init(num_max, mod):
    factorials_mod = dict()
    factorials_mod_inv = dict()
    factorials_mod[0] = 1
    factorials_mod[1] = 1
    factorials_mod_inv[0] = 1
    factorials_mod_inv[1] = 1
    mod_inv = dict()
    mod_inv[1] = 1
    for i in range(2, num_max):
        factorials_mod[i] = factorials_mod[i - 1] * i % mod
        mod_inv[i] = mod - mod_inv[mod % i] * (mod // i) % mod
        factorials_mod_inv[i] = factorials_mod_inv[i - 1] * mod_inv[i] % mod
    return factorials_mod, factorials_mod_inv


def get(num1, num2):
    if num1 > num2:
        num = num2
    else:
        num = num1
    return num_combinations_mod(num1+num2, num, 10**9+7)


answer = 0
if (X + Y) % 3 != 0:
    print(0)
    exit()

total = (X + Y) // 3
n_moveB = (2 * X - Y) // 3
n_moveA = total - n_moveB
answer = get(n_moveA, n_moveB)

print(answer)





### FIXED CODE ###


def num_combinations_mod(n, r, mod, num_max=10**6):
    # if this functions is called twice or more, init process should be placed before calling this function to
    # save time.
    if r > n:
        return 0
    elif r == n:
        return 1
    elif r < 0 or n < 0:
        return 0
    f_mod, f_mod_inv = num_combinations_mod_init(num_max, mod)
    return f_mod[n] * (f_mod_inv[r] * f_mod_inv[n-r] % mod) % mod


def num_combinations_mod_init(num_max, mod):
    factorials_mod = dict()
    factorials_mod_inv = dict()
    factorials_mod[0] = 1
    factorials_mod[1] = 1
    factorials_mod_inv[0] = 1
    factorials_mod_inv[1] = 1
    mod_inv = dict()
    mod_inv[1] = 1
    for i in range(2, num_max):
        factorials_mod[i] = factorials_mod[i - 1] * i % mod
        mod_inv[i] = mod - mod_inv[mod % i] * (mod // i) % mod
        factorials_mod_inv[i] = factorials_mod_inv[i - 1] * mod_inv[i] % mod
    return factorials_mod, factorials_mod_inv


def get(num1, num2):
    if num1 > num2:
        num = num2
    else:
        num = num1
    return num_combinations_mod(num1+num2, num, 10**9+7)


def main(X, Y):
    if (X + Y) % 3 != 0:
        return 0

    total = (X + Y) // 3
    n_moveB = (2 * X - Y) // 3
    n_moveA = total - n_moveB
    answer = get(n_moveA, n_moveB)

    return answer


X, Y = map(int, input().split(" "))
print(main(X, Y))
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))
a=0
for co,i in enumerate(A):
    a+=B[i-1]
    if co>=1 :
        if A[co-1-1]!=N:
            a+=C[A[co-1]-1]
print(a)

### FIXED CODE ###

N=int(input())
print(N**3)
N = list(map(int, input().split()))

print("ABC") if N < 1000 else print("ABD")

### FIXED CODE ###

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

print("ABC") if N[0] < 1000 else print("ABD")
x = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return arr

for number in factorization(x):
  for a in range(x/number):
    b = a - number
    if a**5 - b**5 == x:
      print(a,b)
      break
    elif a**5 - (-b)**5==x:
      print(a,-b)
      break

### FIXED CODE ###

import sys
x = int(input())

for a in range(120):
  for b in range(120):
    if a**5 - b**5 == x:
      print(a,b)
      sys.exit()
    elif a**5 - (-b)**5==x:
      print(a,-b)
      sys.exit()
N = int(input())
A = list(map(int, input().split()))
sa = sorted(A, reverse=True)
ans = 0

for i in range(1, N):
    ans += sa[i//2]

print(ans)


### FIXED CODE ###

# AtCoder
N = int(input())
s = N % 1000
if s != 0:
    print(1000-s)
else:
    print(s)
n,l = list(map(int, input().split(" ")))
s = []
for i in range(n):
  s.append(input())
sort(s)
print("".join(s))

### FIXED CODE ###

n,l = list(map(int, input().split(" ")))
s = []
for i in range(n):
  s.append(input())
s.sort()
print("".join(s))
#!/usr/bin/env python3
import sys
import math

def my_lcm(a: int, b: int):
    return int( abs(a*b) / math.gcd(a, b))

def nr_divide(a: int, b: int, x: int):
    return int(math.floor(b/x)) - int(math.ceil(a/x)) + 1

def solve(A: int, B: int, C: int, D: int):
    E = my_lcm(C, D)
    N = B - A + 1
    nrC = nr_divide(A, B, C)
    nrD = nr_divide(A, B, D)
    nrE = nr_divide(A, B, E)
    count = N - nrC - nrD + nrE
    print(count)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(A, B, C, D)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
from fractions import gcd

def my_lcm(a: int, b: int):
    return  abs(a*b) // gcd(a, b)

def nr_divide(a: int, b: int, x: int):
    count = b//x - a//x + 1
    if a % x != 0:
        count -= 1
    return count

def solve(A: int, B: int, C: int, D: int):
    E = my_lcm(C, D)
    N = B - A + 1
    nrC = nr_divide(A, B, C)
    nrD = nr_divide(A, B, D)
    nrE = nr_divide(A, B, E)
    count = N - nrC - nrD + nrE
    print(count)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(A, B, C, D)
    return

if __name__ == '__main__':
    main()
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

n, m = map(int, input().split())
s = list(input())
t = list(input())

s1 = ['*'] * lcm(n, m)
l = len(s1)

for i in range(n):
    s1[(l//n) * i] = s[i]

for j in range(m):
    if s1[(l//m) * j] != '*' and s1[(l//m) * j] != t[j]:
        print(-1)
        break
    if j == m - 1:
        print(l)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

n, m = map(int, input().split())
s = list(input())
t = list(input())

for i in range(gcd(n, m)):
    if s[i * (n // gcd(n, m))] != t[i * (m // gcd(n, m))]:
        print(-1)
        break
    if i == gcd(n, m) - 1:
        print(lcm(n, m))
N, M = list(map(int, input().split()))
S = input()
T = input()

from fractions import gcd
L = (N * M) // gcd(N, M)

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

if ans:
    print(L)
else:
    print(-1)


# print(L1)
# print(L2)
# print(LS)

### FIXED CODE ###

from fractions import gcd

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

L = (N * M) // gcd(N, M)

L1 = [0]
L2 = [0]

from collections import Counter
c = Counter()

for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t-1)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t-1)


d = {}
for i, li in enumerate(L1):
    d[li] = S[i]

# print(d)

ans = True

for i, li in enumerate(L2):
    if not d.get(li):
        continue
    if d[li] != T[i]:
        ans = False

# print(L1)
# print(L2)
# print(common)
# print(dic)

if ans:
    print(L)
else:
    print(-1)
n,t=map(int,input().split())
a=list(map(int,input().split()))
ans=int(0)
for i in range(0,n):
    if n==i-1:
        ans+=t
        break
    ans+=min(t,a[i+1]-a[i])
print(ans)


### FIXED CODE ###

n,t=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in range(1,n):
    ans+=min(t,a[i]-a[i-1])
ans+=t
print(ans)
n =int(input())
a = list(map(int,input().split()))
if n = len(set(a)):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if len(set(a)) == n:
    print("YES")
else:
    print("NO")