Problem:
 Score : 300 points    Problem Statement You are given a string S of length N and another string T of length M .
These strings consist of lowercase English letters.  A string X is called a good string when the following conditions are all met:   Let L be the length of X . L is divisible by both N and M .  Concatenating the 1 -st, (\frac{L}{N}+1) -th, (2 \times \frac{L}{N}+1) -th, ... , ((N-1)\times\frac{L}{N}+1) -th characters of X , without changing the order, results in S .  Concatenating the 1 -st, (\frac{L}{M}+1) -th, (2 \times \frac{L}{M}+1) -th, ... , ((M-1)\times\frac{L}{M}+1) -th characters of X , without changing the order, results in T .   Determine if there exists a good string. If it exists, find the length of the shortest such string.      Constraints  1 \leq N,M \leq 10^5  S and T consist of lowercase English letters.  |S|=N  |T|=M         Input Input is given from Standard Input in the following format:  N  M  S  T       Output If a good string does not exist, print -1 ; if it exists, print the length of the shortest such string.        Sample Input 1 3 2
acp
ae      Sample Output 1 6  For example, the string accept is a good string.
There is no good string shorter than this, so the answer is 6 .       Sample Input 2 6 3
abcdef
abc      Sample Output 2 -1       Sample Input 3 15 9
dnsusrayukuaiia
dujrunuma      Sample Output 3 45

Solution (Python):
def gcd(a, b):
    if b==0:
        return a
    else:
        return gcd(b, a%b)
N,M = map(int,input().split())
l = gcd(N,M)
S,T = input(),input()
OK = True
for i in range(l):
    ns = i*(N//l)
    nt = i*(M//l)
    if not S[ns]==T[nt]:
        OK = False
print((N*M)//l if OK else -1)

Solution (Python):
a, b = map(int, input().split())

s = input()
t = input()

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

f = 1

for i in range(k):
    if not s[i*(a//k)]==t[i*(b//k)]:
        f = -1
        
if f<0:
    print(-1)
else:
    print(a*b//k)

Solution (Python):
n, m = map(int, input().split())
S = input()
T = input()

def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

l = (n * m) // gcd(n, m)

if S[::l//m] == T[::l//n]:
    print(l)
else:
    print(-1)

Solution (Python):
import fractions

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

g = fractions.gcd(N, M)

lcm = N * M // g

ln = lcm // N
lm = lcm // M

count_n = 0
count_m = 0

while count_n != N and count_m != M:

    temp_n = count_n * ln
    temp_m = count_m * lm

    if temp_n == temp_m:
        if S[count_n] != T[count_m]:
            print(-1)
            break
    
    if count_n == (N - 1):
        count_m += 1
    elif count_m == (M - 1):
        count_n += 1
    elif temp_n <= temp_m:
        count_n += 1
    else:
        count_m += 1
else:
    print(lcm)

Solution (Python):
ls, lt = map(int, input().split())
s = list(input())
t = list(input())
def gcd(m,n):
    if n == 0:
        return m
    else:
        return gcd(n,m%n)
g = gcd(ls,lt)
m = ls // g
n = lt // g
ret = g*m*n
for i in range(g):
    if s[i*m] != t[i*n]:
        ret = -1
        break
print(ret)

Solution (Python):
def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

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

n, m = map(int, input().split())
S = input()
T = input()

l = lcm(n, m)
        
if S[::n // gcd(n, m)] == T[::m // gcd(n, m)]:
    print(l)
else:
    print(-1)

Solution (Python):
N,M=map(int,input().split())
n,m=N,M
s=input()
t=input()
while m:
  n,m=m,n%m
gcd=n
lcm=N*M//gcd
step1=N//gcd
step2=M//gcd
if all(s[i*step1]==t[i*step2] for i in range(gcd)):
  print(lcm)
else:
  print(-1)

Solution (Python):
def gcd(a,b):
    if a==b:
        return b
    elif a%b == 0:
        return b
    else:
        return gcd(b,a%b)

n,m = map(int,input().split())
s = input()
t = input()
if n<m:
    tmp = m
    m = n
    n = tmp
    tmp = s
    s = t
    t = tmp
lcm = (n*m)//gcd(n,m)
ok = True
if s[0] != t[0]:
    ok = False

for i in range(1,gcd(n,m)-1):
    if s[n//gcd(n,m)*i] != t[m//gcd(n,m)*i]:
        ok = False
        break
print(lcm if ok else -1)

Solution (Python):
N,M=map(int,raw_input().split())
S=raw_input()
T=raw_input()

def gcd(m,n):
    x=max(m,n)
    y=min(m,n)
    if x%y==0:
        return y
    else:
        while x%y!=0:
            z=x%y
            x=y
            y=z
        else:
            return z
            

X=N*M/gcd(N,M)
double=[[(X/M)*i,(X/N)*i] for i in range(N*M/X)]
print X if all(S[d[0]]==T[d[1]] for d in double) else "-1"

Solution (Python):
N, M = map(int, input().split())
S = input()
T = input()


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

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

if S[0::length//M] == T[0::length//N]:
    print(length)
else:
    print(-1)

Solution (Python):
import fractions
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
S = input(); T = input()
gcd = fractions.gcd(N,M)
N_prime = N //gcd; M_prime = M // gcd
for i in range(0,N,N_prime):
    for j in range(0,M,M_prime):
        if i * M_prime - j * N_prime == 0 and S[i] != T[j]:
            print(-1)
            exit()
print(N*M // gcd)

Solution (Python):
import fractions
N,M = map(int,input().split())
S = input(); T = input()
gcd = fractions.gcd(N,M)
N_prime = N //gcd; M_prime = M // gcd
for i in range(0,N,N_prime):
    for j in range(0,M,M_prime):
        if i * M_prime - j * N_prime == 0 and S[i] != T[j]:
            print(-1)
            exit()
print(N*M // gcd)

Solution (Python):
from fractions import gcd
N,M = map(int,input().split())
S = input()
T = input()
g = gcd(N,M)
ans = N*M//g
print(ans if S[::N//g] == T[::M//g] else -1)

Solution (Python):
import sys

def gcd(a,b):
    if b==0:
        return a
    return(gcd(b, a%b))

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

N, M = map(int,input().split())
S = input()
T = input()
d = gcd(N,M)
L = lcm(N,M)
for i in range(d):
    if S[i*(N//d)] != T[i*(M//d)]:
        print(-1)
        sys.exit()

print(L)

Solution (Python):
N,M = map(int,input().split())
S = input()
T = input()
ans = 0
a = 2

if S[0] != T[0]:ans = -1

elif N % M != 0 and M % N != 0:
    if N >= M:
        while True:
            if N * a % M == 0:
                ans = N * a
                b = int(N*a/M)
                for i in range(int(N/b)):
                    if T[a*i] != S[b*i]:
                        ans = -1
                        break
                break
            else:
                a += 1
    elif N < M:
        while True:
            if M * a % N == 0:
                ans = M * a
                b = int(M*a/N)
                for i in range(int(M/b)):
                    if T[b*i] != S[a*i]:
                        ans = -1
                        break
                break
            else:
                a += 1

elif N % M == 0:
    b = int(N/M)
    ans = N
    for i in range(M):
        if T[i] != S[b*i]:
            ans = -1
            break   

elif M % N == 0:
    b = int(M/N)
    ans = M
    for i in range(N):
        if S[i] != T[b*i]:
            ans = -1
            break   

print(ans)

Solution (Python):

from fractions import gcd
import sys

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

d = gcd(N, M)
m = N * M // d

for i in range(d):
    if S[i * (N // d)] != T[i * (M // d)]:
        print(-1)
        sys.exit()

print(m)

Solution (Python):
import numpy as np
def eucrid(a, b):
	if (a > b):
		buf = a
		a = b
		b = buf
	if (b % a == 0):
		return a
	else:
		return eucrid(b%a, a)
		
def main():
	buf = input().split()
	s = input()
	t = input()
	n = len(s)
	m = len(t)
	
	big = n*m//eucrid(n, m)
	flag = big
	"""
	for i in range(big):
		if (i%(big//n) == 0 and i%(big//m) == 0):
			
			
			if(s[(i+1)//(big//n)] != t[(i+1)//(big//m)]):
				flag = -1
	"""			
	for i in range(n):
		if((i*(big//n))%(big//m) == 0):
			if(s[i] != t[(i*(big//n))//(big//m)]):
				flag = -1

	print(flag)
	
	
	
main()

Solution (Python):
from fractions import gcd
N, M = map(int, input().split(" "))
S = input()
T = input()
G = gcd(N, M)
L = N * M // G
for i in range(G):
  if S[i*N//G] != T[i*M//G]:
    print(-1)
    exit(0)
print(L)

Solution (Python):
import fractions
n,m = map(int,input().split())
s=input()
t=input()
def answer(n,m,s,t):
    if s[0] != t[0]:
        return -1
    g = fractions.gcd(n,m)
    l = n*m//g
    i = 1
    while l*i < m*n:
        if s[l*i//m] != t[l*i//n]:
            return -1
        else:
            i += 1
    return l
print(answer(n,m,s,t))

Solution (Python):
n,m=map(int,input().split())
s=input()
t=input()

import fractions

def agc(n,m,s,t):
    if s[0]!=t[0]:
        return -1
    g=fractions.gcd(n,m)
    if g==1:
        return  n*m
    l=n*m//g
    i=1
    while l*i<m*n:
        if s[int(l*i//m)]!=t[int(l*i//n)]:
            return -1
        i+=1
    return  int(l)
print(agc(n,m,s,t))

Solution (Python):

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


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


N, M = [int(elem) for elem in input().split()]
S = input()
T = input()

L = lcm(N, M)
m, n = L // N, L // M

for i in range(N):
    if i % n == 0:
        S_idx = i
        T_idx = m * i // n
        if S[S_idx] != T[T_idx]:
            print(-1)
            exit(0)

for i in range(M):
    if i % m == 0:
        S_idx = n * i // m
        T_idx = i
        if S[S_idx] != T[T_idx]:
            print(-1)
            exit(0)
else:
    print(L)

Solution (Python):
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a
 
x,y=map(int,input().split())
S=input()
T=input()
GCD=gcd(x,y)
LCM=(x * y) // GCD
 
x_new=x//GCD
y_new=y//GCD
for i in range(0,GCD):
  if S[(x_new)*i]==T[(y_new)*i]:
    result=LCM
  else:
    result=-1
    break
print(result)

Solution (Python):
N, M = map(int, input().split())
S = input(); T = input()

def gcd(n, m):
    if n < m:
        return gcd(m, n)
    if m == 0:
        return n
    else:
        return gcd(m, n % m)

nm_gcd = gcd(N, M)
n, m = M // nm_gcd, N // nm_gcd
ans = N * M // nm_gcd
for i in range(nm_gcd):
    if S[i * m] != T[i * n]:
        ans = -1
        break

print(ans)

Solution (Python):
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a

x,y=map(int,input().split())
S=input()
T=input()
GCD=gcd(x,y)
LCM=(x * y) // GCD

x_new=x//GCD
y_new=y//GCD
for i in range(0,GCD):
  if S[(x_new)*i]==T[(y_new)*i]:
    result=LCM
  else:
    result=-1
    break
print(result)

Solution (Python):
class MathAlgo(object):

    @classmethod
    def gcd(cls, a, b):
        if b == 0:
            return a
        else:
            return cls.gcd(b, a%b)


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

base = MathAlgo.gcd(N,M)

for i in range(base):
    if S[len(S) //base *i] != T[len(T) //base *i]:
        print(-1)
        break
else:
    print(N //base *M)

Solution (Python):
import fractions


def two_abbreviation(n, m, s, t):
    common = int(fractions.gcd(n, m) + 10 ** -6)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    ret = int(n * m / common + 10 ** -6) if s_common == t_common else -1
    return ret


N, M = [int(a) for a in input().split()]
S = str(input())
T = str(input())

print(str(two_abbreviation(N, M, S, T)))

Solution (Python):
N, M = [int(_) for _ in input().split()]
S = input()
T = input()


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


g = gcd(N, M)
if (g == 1 and S[0] == T[0]) or S[::N // g] == T[::M // g]:
    print(N * M // g)
else:
    print(-1)

Solution (Python):
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
l=lcm(n,m)
d={}
f=l
for i in range(max(n,m)):
    o=i*(l//n)
    p=i*(l//m)
    if i<n and o not in d:
        d[o]=s[i]
    elif i<n and o in d and d[o]!=s[i]:
        f=-1
    if i<m and p not in d:
        d[p]=t[i]
    elif i<m and p in d and d[p]!=t[i]:
        f=-1
print(f)

Solution (Python):
from fractions import gcd 

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

N,M = map(int, input().split())
S = input()
T = input()
L= lcm(N,M)
ans = dict()
for i in range(N):
    idx = i*(L//N)
    ans[idx] = S[i]

for j in range(M):
    idx = j*(L//M)
    if idx in ans.keys():
        if ans[idx]==T[j]:
            continue
        else:
            print(-1)
            break
else:
    print(L)

Solution (Python):
import sys


def next_str() -> str:
    result = ""
    while True:
        tmp = sys.stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


def next_int() -> int:
    return int(next_str())


def gcd(x: int, y: int) -> int:
    if x < y:
        return gcd(y, x)
    elif y == 0:
        return x
    else:
        return gcd(y, x % y)


def lcm(x: int, y: int) -> int:
    return x * y // gcd(x, y)


def main() -> None:
    n, m = [next_int() for _ in range(2)]
    s, t = [next_str() for _ in range(2)]
    l = lcm(n, m)
    dic = dict()

    for i, c in enumerate(s):
        j = i * l // n
        dic[j] = c

    for i, c in enumerate(t):
        j = i * l // m
        if j in dic and dic[j] != c:
            print(-1)
            return

    print(l)


if __name__ == '__main__':
    main()

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

N, M = inpl()
gcdnm = gcd(N, M)
S = input()
T = input()
S = ''.join([S[i*(N//gcdnm)] for i in range(gcdnm)])
T = ''.join([T[i*(M//gcdnm)] for i in range(gcdnm)])
if S == T:
    print(N*M//gcdnm)
else:
    print(-1)

Solution (Python):
from fractions import gcd

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

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

gcded = gcd(N,M)
n = N//gcded
m = M//gcded
for i in range(gcded):
  if S[i*n] != T[i*m]:
    print(-1)
    exit()

print(L)

Solution (Python):
n, m = map(int,input().split())
s = input()
t = input()
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
g = gcd(n, m)
l = n * m // g
for i in range(0, g):
  if s[i * n//g] != t[i * m//g]:
    print('-1')
    exit()
print(l)

Solution (Python):
import fractions
n, m = map(int,input().split())
s = input()
t = input()
q = fractions.gcd(n, m)
l = n * m // q 
for i in range(0, q):
  if s[i * n//q] != t[i * m//q]:
    print('-1')
    exit()
print(l)

Solution (Python):
import fractions
n, m = map(int,input().split())
s = input()
t = input()
q = fractions.gcd(n, m)
l = n * m // q 
p = int(l/n * l/m / fractions.gcd(l/n, l/m)) 
for i in range(0, int(l/p)):
  if s[i * p//(l//n)] != t[i * p//(l//m)]:
    print('-1')
    exit()
print(l)

Solution (Python):
import fractions
n, m = map(int,input().split())
s = list(map(str,input()))
t = list(map(str,input()))
k = 0
q = fractions.gcd(n, m)
l = n * m // q 
p = int(l/n * l/m / fractions.gcd(l/n, l/m)) 
for i in range(0, int(l/p)):
  if s[i * p//(l//n)] != t[i * p//(l//m)]:
    print('-1')
    exit()
print(l)

Solution (Python):
import fractions
n, m = map(int,input().split())
s = list(map(str,input()))
t = list(map(str,input()))
k = 0
q = fractions.gcd(n, m)
l = n * m // q 
p = int(l/n * l/m / fractions.gcd(l/n, l/m)) 
for i in range(0, int(l/p)):
  if s[i * p//(l//n)] != t[i * p//(l//m)]:
    print('-1')
    break
  else:
    k = k + 1

if k == l/p:
  print(l)

Solution (Python):
import fractions
n, m = map(int,input().split())
s = list(map(str,input()))
t = list(map(str,input()))
k = 0
q = fractions.gcd(n, m)
l = n * m // q 
p = int(l/n * l/m / fractions.gcd(l/n, l/m)) 
for i in range(0, int(l/p)):
  if s[0] != t[0]:
    print('-1')
    break
  elif q == 1:
    print(l)
    break
  elif s[i * p//(l//n)] != t[i * p//(l//m)]:
    print('-1')
    break
  else:
    k = k + 1

if k == l/p:
  print(l)

Solution (Python):
def gcd(a,b):
    while b>0:
        a,b = b, a%b
    return a

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

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

g = gcd(n,m)
for i in range(g):
    if s[n//g*i] != t[m//g*i]:
        print(-1)
        exit()
print(lcm(n,m))

Solution (Python):
N,M=map(int,input().split())
S=input()
T=input()
list_S=list(S)
list_T=list(T)
Number_i=[i for i in range(N)]
Number_iMN=[]
for i in Number_i:
  Number_iMN.append(i*M/N)
Number_j=[j for j in range(M)]
Kaburi_j=list(set(Number_iMN)&set(Number_j))
Kaburi_i=[]
for j in Kaburi_j:
  Kaburi_i.append(int(j*N/M))
counter=0
Flag=0
Kaburi_Size=len(Kaburi_i)
while counter<=Kaburi_Size-1:
  if list_S[int(Kaburi_i[counter])]==list_T[int(Kaburi_j[counter])]:
    pass
  else:
    Flag=1
    break
  counter+=1
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a
if Flag==1:
  print(-1)
else:
  print(int(N*M/gcd(N,M)))

Solution (Python):
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


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

    g = gcd(N, M)
    for i in range(g):
        if S[i * N // g] != T[i * M // g]:
            print("-1")
            exit()
    print(N * M // g)

main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    s = S()
    t = S()
    l = n * m // fractions.gcd(n,m)
    si = ti = 0
    sc = l // n
    tc = l // m
    while si < l and ti < l:
        if si == ti:
            if s[si//sc] != t[ti//tc]:
                return -1
            si += sc
            ti += tc
        elif si < ti:
            si += sc
        else:
            ti += tc

    return l


print(main())

Solution (Python):
import fractions
n, m = map(int,input().split())
s = input()
t = input()
g = fractions.gcd(n, m)
l =  n * m // g
flag = True

for i in range(g):
    if s[i * n // g] != t[i * m // g]:
        flag = False

if flag:
    print(l)
else:
    print(-1)

Solution (Python):
import sys
def euclid(data):
    a=data[0]
    for b in data[1:]:
        if(b<a):
            a,b=b,a
        while(1):
            r=b%a
            if(r==0):
                break
            else:
                b=a
                a=r
    return a


S_l,T_l=map(int,input().split())
S=input()
T=input()

lcm=S_l*T_l//euclid([S_l,T_l])
dS=lcm//S_l
dT=lcm//T_l

llcm=dS*dT//euclid([dS,dT])
ddS=llcm//dS
ddT=llcm//dT

i=0
while(ddS*i < S_l and ddT*i < T_l):
    if(S[ddS*i]!=T[ddT*i]):
        print(-1)
        sys.exit(0)
    i+=1
print(lcm)

Solution (Python):
N, M = map(int, input().split())
S = input()
T = input()
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

gc = gcd(max(N, M), min(N, M))
for i in range(gc):
    if S[i*N//gc] != T[i*M//gc]:
        print(-1)
        exit()
print(N*M//gc)

Solution (Python):
import math

 

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


def lcd(n,m):
    return int(n * m / gcd(n,m))
def gcd(n,m):
    if n % m == 0:
        return m
    else:
        return gcd(m,n % m)

    
def prove(n,m):
    n_i = int(lcd(n,m)/n)
    m_i = int(lcd(n,m)/m)
    n_list=[S[m_i*i] for i in range(gcd(n,m))]
    m_list=[T[n_i*i] for i in range(gcd(n,m))]


    if n_list==m_list:
        return lcd(n,m)
    else:
        return -1


print(prove(N,M))

Solution (Python):
import math

 

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


def lcd(n,m):
    return int(n * m / gcd(n,m))
def gcd(n,m):
    if n % m == 0:
        return m
    else:
        return gcd(m,n % m)

    
def prove(n,m):
    n_i = int(n/gcd(n,m))
    m_i = int(m/gcd(n,m))
    n_list,m_list=[],[]
    for i in range(gcd(n,m)):
        n_list += S[i*n_i]
        m_list += T[i*m_i]


    if n_list==m_list:
        return lcd(n,m)
    else:
        return -1


print(prove(N,M))

Solution (Python):
import math

 

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

pair = {N:S,M:T}


def lcd(n,m):
    return int(n * m / gcd(n,m))
def gcd(n,m):
    if n % m == 0:
        return m
    else:
        return gcd(m,n % m)

    
def prove(n,m):
    if gcd(n,m)==1:
        return lcd(n,m)
    global pair
    n_i = int(n/gcd(n,m))
    m_i = int(m/gcd(n,m))
    n_list = pair[n][::n_i]
    m_list = pair[m][::m_i]


    if n_list[0:len(m_list)]==m_list:
        return lcd(n,m)
    else:
        return -1
n = max(pair.keys())
m = min(pair.keys())
if pair[N][0]!=pair[M][0]:
    print(-1)
elif N==M:
    if S==T:
        print(N)
    else:
        print(-1)
else:
    print(prove(n,m))

Solution (Python):
from fractions import gcd

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

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

lenS,lenT = len(S),len(T)
L = lcm(N,M)
isok = True
for i in range(L):
    if i*(L//M)>=len(S) or i*(L//N)>=len(T):
        break
    elif S[i*(L//M)]!=T[i*(L//N)]:
        isok = False
        break
        
if isok:
    print(L)
else:
    print("-1")

Solution (Python):
def gcd(x, y):
  if y == 0:
    return x
  return gcd(y, x % y)
N, M = map(int, input().split())
S = input()
T = input()
g = gcd(N, M)
ans = int(N * M / g)
for i in range(g):
  if S[int(N / g * i)] != T[int(M / g * i)]:
    ans = -1
    break
print(ans)

Solution (Python):
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

N, M = map(int, input().split())
S = input()
T = input()
g = gcd(N, M)
for i in range(g):
    if S[i*N//g] != T[i*M//g]:
        print(-1)
        break
else:
    print(N*M//g)

Solution (Python):
def gcd(a, b):
    if a>b:
        c = a%b
    else:
        c = b%a
    if c==0:
        return b
    else:
        return gcd(b,c)

[n,m]=[int(i) for i in input().split()]
s=input()
t=input()
g=gcd(n,m)

lcm=int(n*m/g)

s1=int(lcm/n)
s2=int(lcm/m)



f=1
for i in range(int(n/s2)):
    
    if s[s2*i] != t[s1*i]:
        f=0

if f:
    print(lcm)
else:
    print("-1")

Solution (Python):
n, m = map(int, raw_input().split())
s = raw_input()
t = raw_input()

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

L = n * m / gcd(n, m)

a = {}
for i in range(n):
    a[i * L / n] = s[i]

poss = True
for j in range(m):
    idx = j * L / m
    if idx in a:
        poss &= a[idx] == t[j]

if poss:
    print L
else:
    print -1

Solution (Python):
def get_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def get_lcm(a, b, gcd=0):
    if gcd == 0:
        return a * b // get_gcd(a, b)
    else:
        return a * b // gcd


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

S = input()
T = input()

gcd = get_gcd(N, M)
lcm = get_lcm(N, M, gcd)

if [s for i, s in enumerate(S) if i % (lcm / M) == 0] == [t for i, t in enumerate(T) if i % (lcm / N) == 0]:
    print(lcm)
else:
    print(-1)

Solution (Python):
n,m = (int(i) for i in input().split())
s = input()
t = input()
def gcd(a,b):
	if a%b: return gcd(b,a%b)
	else: return b
g = gcd(n,m)
ng, mg = n//g, m//g
if all(s[i*ng] == t[i*mg] for i in range(g)) :
    print(n*m//g)
else :
    print(-1)

Solution (Python):
def gcd(a, b):
    if b > a:
        gcd(b, a)
    while b:
	    a, b = b, a % b
    return a

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

l = n * m // gcd(n, m)
a = l // n
b = l // m


res = False
clear_all = True
for i in range(1,n+1):
    if (a*i - (a-b)) % b == 0:
        j = (a * i - (a-b)) // b
        if not s[i-1] == t[j-1]:
            clear_all = False
if clear_all:
    res = True
if res:
    print(l)
else:
    print(-1)

Solution (Python):
import sys

def gcd(a,b):
    if a<b:
        a,b = b,a
    if a%b==0:
        return b
    else:
        return gcd(a%b,b)
        
N,M=map(int,input().split())
length=N*M//gcd(N,M)

S=input()
T=input()

a=length//N
b=length//M
l=a*b//gcd(a,b)
s=l//a
t=l//b

for i in range(gcd(N,M)):
    if S[i*s]!=T[i*t]:
        print(-1)
        sys.exit()
print(length)

Solution (Python):
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
g=gcd(n,m)
a=n//g
b=m//g
for i in range(g):
  if s[a*i]!=t[b*i]:
    print(-1)
    break
else:
  print(n*m//g)

Solution (Python):
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
g=gcd(n,m)
a=n//g
b=m//g
for i in range(g):
  if s[a*i]!=t[b*i]:
    print(-1)
    break
else:
  print(n*m//g)

Solution (Python):
from fractions import gcd
import sys
N,M=map(int,input().split())
S=input()
T=input()
a=gcd(M,N)
m=M//a
n=N//a
for i in range(a):
    if S[n*i]!=T[m*i]:
        print(-1)
        sys.exit()
print(m*N)

Solution (Python):


import sys


input = sys.stdin.readline
INF = float('inf')


def inpl(): return list(map(int, input().split()))



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



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


def solve(N, M, S, T):
    L = lcm(N, M)
    ln, lm = L // N, L // M

    
    
    
    D = lcm(ln, lm)
    A = D // ln
    B = D // lm
    for i in range(gcd(N, M)):
        if S[A * i] != T[B * i]:
            break
    else:
        return L
    return -1


N, M = inpl()
S = input()
T = input()
print(solve(N, M, S, T))

Solution (Python):
n,m=map(int,input().split());g=m-max([a*n%m for a in range(m)]);print(-1if input()[::n//g]!=input()[::m//g]else n*m//g)

Solution (Python):


import sys


input = sys.stdin.readline
INF = float('inf')


def inpl(): return list(map(int, input().split()))



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



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


def solve(N, M, S, T):
    L = lcm(N, M)
    ln, lm = L // N, L // M

    
    
    
    
    D = lcm(ln, lm)

    li_S = []
    for i in range(0, N, D // ln):
        li_S.append(S[i])

    li_T = []
    for i in range(0, M, D // lm):
        li_T.append(T[i])

    
    
    if li_S == li_T:
        return L
    else:
        return -1


N, M = inpl()
S = input()
T = input()
print(solve(N, M, S, T))

Solution (Python):


def gcd(a, b):
    if a < b:
        a, b = b, a

    if b == 1:
        return 1
    m = a % b
    if m == 0:
        return b
    return gcd(b, m)


def main():
    N, M = [int(a) for a in input().split()]

    S = input()
    T = input()
    L = N * M // gcd(N, M)
    a1 = L // N
    a2 = L // M
    cc = a1 * a2 // gcd(a1, a2)
    for i in range(0, L, cc):
        if S[i // a1] != T[i // a2]:
            print(-1)
            return
    print(L)


if __name__ == '__main__':
    main()

Solution (Python):
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

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

n, m = map(int, input().split())
s = input()
t = input()
L = lcm(n, m)
l = lcm(L // n, L // m)
for i in range(0, L, l):
    if s[i // (L // n)] != t[i // (L // m)]:
        print(-1)
        exit()
print(L)

Solution (Python):
n, m = map(int, input().split())

s = list(input())
t = list(input())

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

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

l = lcm(n,m)


step = l // n
step_m = l // m
for i in range(n):
    if (step * i) % step_m == 0:
        if s[i] != t[(step * i) // step_m]:
            
            print(-1)
            exit()

print(l)

Solution (Python):
import numpy as np
from fractions import gcd
 
 
N, M = list(map(int, input().split()))
S = input()
T = input()

g = gcd(N, M)
l = int(N * M / g)

for i in range(g):
    if S[int(N/g*i)] != T[int(M/g*i)]:
        l = -1
        break

print(l)

Solution (Python):
import fractions
n,m=map(int, input().split())
s=input()
t=input()
f=fractions.gcd(n,m)
ans=n*m//f
for i in range(f):
    if s[n//f*i]!=t[m//f*i]:ans=-1
print(ans)

Solution (Python):



def lcm(x: int, y: int):
    '''
    See:
    https://note.nkmk.me/python-gcd-lcm/
    '''
    from fractions import gcd
    return (x * y) // gcd(x, y)


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    size = lcm(n, m)
    part_s = [s[i] for i in range(0, n, size // m)]
    part_t = [t[j] for j in range(0, m, size // n)]

    for si, ti in zip(part_s, part_t):
        if si != ti:
            print(-1)
            exit()

    print(size)


if __name__ == '__main__':
    main()

Solution (Python):
n,m = map(int,input().split())
s = str(input())
t = str(input())
def get_gcd(a, b): 
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return get_gcd(b, a % b)
def get_lcm(a, b, gcd): 
    lcm = a * b // gcd
    return lcm
lcm = get_lcm(n,m,get_gcd(n,m)) 
lcm2 = get_lcm(lcm/n,lcm/m,get_gcd(lcm/n,lcm/m)) 
ans = 0
for i in range(int(lcm//lcm2)):
    if s[int(i*lcm2//(lcm/n))] == t[int(i*lcm2//(lcm/m))]:
        pass
    else:
        ans = 1
        break
if ans == 1:
    print(-1)
else:
    print(lcm)

Solution (Python):

N, M = [int(_) for _ in input().split()]
S = input()
T = input()

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

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

cs = {}

for i in range(N):
    cs[L // N * i + 1] = S[i]

result = L

for i in range(M):
    j = L // M * i + 1
    if j in cs and cs[j] != T[i]:
        result = -1
        break

print(result)

Solution (Python):



def lcm(x: int, y: int):
    '''
    See:
    https://note.nkmk.me/python-gcd-lcm/
    '''
    from fractions import gcd
    return (x * y) // gcd(x, y)


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    size = lcm(n, m)
    dn = size // n
    dm = size // m
    part_s = list()
    part_t = list()

    for i in range(0, n, dm):
        part_s.append(s[i])

    for i in range(0, m, dn):
        part_t.append(t[i])

    for si, ti in zip(part_s, part_t):
        if si != ti:
            print(-1)
            exit()

    print(size)


if __name__ == '__main__':
    main()

Solution (Python):



def lcm(x: int, y: int):
    '''
    See:
    https://note.nkmk.me/python-gcd-lcm/
    '''
    from fractions import gcd
    return (x * y) // gcd(x, y)


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    size = lcm(n, m)
    dn = size // n
    dm = size // m
    part_s = [s[0]]
    part_t = [t[0]]
    i = dm
    j = dn

    while i < n:
        part_s.append(s[i])
        i += dm

    while j < m:
        part_t.append(t[j])
        j += dn

    for si, ti in zip(part_s, part_t):
        if si != ti:
            print(-1)
            exit()

    print(size)


if __name__ == '__main__':
    main()

Solution (Python):
N, M =  map(int, input().split(' '))
def gcd(a, b):
    a, b = (a, b) if a >= b else (b, a)
    while b > 0:
        a, b = b, a % b
    return a

S = input()
T = input()
g = gcd(N, M)



if S[0::N//g] == T[0::M//g]:
    print(N*M//g)
else:
    print(-1)

Solution (Python):
N, M = map(int, input().split())
S = input()
T = input()

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if x % y == 0:
        return y
    else:
        return gcd(y,x%y)

def lcm(m,n):
    return int(m * n /gcd(m,n))

d = gcd(N,M)
l = lcm(N,M)

s = [0 for i in range(0,d)]
t = [0 for i in range(0,d)]

a = int(l/M)
b = int(l/N)

for i in range(0,d):
    s[i] = S[i*a]
    t[i] = T[i*b]

if s == t:
    print(l)
else:
    print(-1)