Harryxun/stf_run huggingface dataset:
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

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

L = [0]*N
R = [0]*N

L[0] = A[0]
r[-1] = A[-1]

for i in range(1, N):
	L[i] = gcd(L[i], A[i])
	idx = N-1-i
	R[i] = gcd(R[idx], A[idx])

#残りの N − 1 個の整数の最大公約数
mx = 0
for i in range(N):
	if i==N-1:	#後ろから1個めが抜かれた時
		v = L[N-2]
	elif i==0:	#前から1個めが抜かれた時
		v = R[1]
	else:		#どれでもない時
		v = gcd(L[i+1], R[i-1])
	mx = max(v, mx)
print(mx)


### FIXED CODE ###

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

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

N = int(input())
A = [int(a) for a in input().split()]

# GCDの結合則を利用する
# 左端、右端からの累積GCDを求めておくと、Aiを取り除いた場合のGCDがすぐに計算できる。
# つまり、
# L(i): n=0,...,iまでのGCD 
# R(i): n=i,...,N-1までのGCD
# このとき、Aiを除いた全体のGCDは、GCD(L(i-1), R(i+1))で計算できる。

L = [0] * N
R = [0] * N

L[0] = A[0]
R[-1] = A[-1]
for i in range(1, N):
    L[i] = gcd(L[i-1], A[i])
    idx = N-1-i
    R[idx] = gcd(R[idx+1], A[idx])

mx = 0
for i in range(N):
    if i == N-1:
        v = L[N-2]
    elif i == 0:
        v = R[1]
    else:
        v = gcd(R[i+1], L[i-1])
    mx = max(v, mx)
print(mx)
n=input()
l = [int(x) for x in list(str(n))]
print(l.replace("1","9").replace("9","1"))


### FIXED CODE ###

print(input().replace("1","*").replace("9","1").replace("*","9"))
s1 = input()
s2 = input()
print(s2 + s1)

### FIXED CODE ###

s1 = input().split()
s1 = s1[::-1]
print("".join(s1))
input()
D = {}
for a in [int(a) for a in input().split()]:
    if a not in D: D[i] = 0
    D[i] += 1

input()
for a in [int(a) for a in input().split()]:
    if a not in D: D[i] = 0
    D[i] -= 1

for a in D:
    if D[a] < 0:
        print("NO")
        break
else:
    print("YES")

### FIXED CODE ###

input()
D = {}
for a in [int(a) for a in input().split()]:
    if a not in D: D[a] = 0
    D[a] += 1

input()
for a in [int(a) for a in input().split()]:
    if a not in D: D[a] = 0
    D[a] -= 1

for a in D:
    if D[a] < 0:
        print("NO")
        break
else:
    print("YES")
import sys

b={}
for s in sys.stdin:
    i = s[s.index(',')+1:-1]
    try: b[i]+=1
    except: b[i]=1
for e in [0,1,3,2]:
    print b[b.keys()[e]]

### FIXED CODE ###

import sys

b=[s.split(',')[1][:-1] for s in sys.stdin]
for e in ["A","B","AB","O"]:
    print b.count(e)
a,b,c = map(int,input().split())
if (x-a)<b:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a,b,x = map(int,input().split())
if (x-a)<=b and x>=a:
    print("YES")
else:
    print("NO")
def gcd(x, y):
	if x < y:
		x, y = y, x
	if y == 0:
		return x
	z = x % y
	return gcd(y, z) 
	
N=int(input())
prenum = 1
for i in range(N):
	T = int(input())
	lcm = (prenum / gcd(T, prenum)) * T
	prenum = lcm
print(int(lcm))

### FIXED CODE ###

def gcd(x, y):
	if x < y:
		x, y = y, x
	if y == 0:
		return x
	z = x % y
	return gcd(y, z) 
	
N=int(input())
prenum = 1
for i in range(N):
	T = int(input())
	lcm = prenum // gcd(prenum, T) * T
	prenum = lcm
print(lcm)
a, b, c = map(int,input().split())
print(max(0,c - (a - b))

### FIXED CODE ###

a, b, c = map(int,input().split())
print(max(0,c-a+b))
N,X=map(int,input().split())
x=list(map(int,input().split()))
l=[]
for i in range(N):
    l.append(abs(X-x[i]))
from hase import gcd

ll=[0]*(N+1)
for i in range(N):
    ll[i+1]=gcd(ll[i],l[i])
print(ll[N])


### FIXED CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))
l=[]
for i in range(N):
    l.append(abs(X-x[i]))
def gcd(a,b):
    if a == 0:
        return b
    if b == 0:
        return a
    r = 1
    while r > 0:
        r = a % b
        a = b
        b = r
    return a

ll=[0]*(N+1)
for i in range(N):
    ll[i+1]=gcd(ll[i],l[i])
print(ll[N])
from collections import Counter
n = int(input())
b = [input() for _ in range(n)]
m = int(input())
r = [input() for _ in range(m)]

db = Counter(b)
dr = Counter(r)

print(max(*(v-dr[k] for k, v in db.items()), 0))


### FIXED CODE ###

from collections import Counter

n = int(input())
b = [input() for _ in range(n)]
m = int(input())
r = [input() for _ in range(m)]

db, dr = [Counter(x) for x in (b, r)]
print(max(*[v-dr[k] for k, v in db.items()]+[0]))
pink = 0
green = 0
white = 0
yellow = 0

n = input()
l = raw_input().split()
 
for i in range(n):
   
    if(l[i] == 'P'):
        pink = 1

    if(l[i]== 'G'):
        green = 1

    if(l[i] == 'W'):
        white = 1

    if(l[i] == 'Y'):
        yellow = 1

if(pink + white + green + yellow) == 4:
    print('Four')
else:
    print('Three')


### FIXED CODE ###

n = 0

n = input()

ans = 0

ans = n/3

print(ans)
N,K,C=map(int,input().split())
S=input()
i=0
data1=[0 for i in range(0,N)]
if S[0]=='o':
    for j in range(0,C+1):
        data1[j]=(1,C+1)
    i=C+1
else:
    data1[0]=(0,1)
    i=1
while N-1>=i:
    if S[i]=='o':
        for j in range(0,C+1):
            if N>i+j:
                data1[i+j]=(data1[i-1][0]+1,min(i+C+1,N))
        i+=C+1
    else:
        data1[i]=(data1[i-1][0],i+1)
        i+=1

data2=[0 for i in range(0,N)]
if S[-1]=='o':
    for j in range(0,C+1):
        data2[j]=1
    i=C+1
else:
    data2[0]=1
    i=1
while N-1>=i:
    if S[-i-1]=='o':
        for j in range(0,C+1):
            if N>i+j:
                data2[i+j]=data2[i-1]+1
        i+=C+1
    else:
        data2[i]=data2[i-1]
        i+=1

for i in range(0,N):
    if S[i]=='o':
        if i==0:
            if K>data2[N-2]:
                print(i+1)
        elif N-1>i:
            work,nextday=data1[i-1]
            if nextday!=N:
                nextday=max(nextday,i+1)
                if K>work+data2[N-1-nextday]:
                    print(i+1)
            else:
                if K>work:
                    print(i+1)
        elif i==N-1:
            if K>data1[N-2][0]:
                print(i+1)

### FIXED CODE ###

N,K,C=map(int,input().split())
S=input()
i=0
data1=[0 for i in range(0,N)]
if S[0]=='o':
    for j in range(0,C+1):
        if N>j:
            data1[j]=(1,min(N,C+1))
    i=C+1
else:
    data1[0]=(0,1)
    i=1
while N-1>=i:
    if S[i]=='o':
        for j in range(0,C+1):
            if N>i+j:
                data1[i+j]=(data1[i-1][0]+1,min(i+C+1,N))
        i+=C+1
    else:
        data1[i]=(data1[i-1][0],i+1)
        i+=1

data2=[0 for i in range(0,N)]
if S[-1]=='o':
    for j in range(0,C+1):
        if N>j:
            data2[j]=1
    i=C+1
else:
    data2[0]=0
    i=1
while N-1>=i:
    if S[-i-1]=='o':
        for j in range(0,C+1):
            if N>i+j:
                data2[i+j]=data2[i-1]+1
        i+=C+1
    else:
        data2[i]=data2[i-1]
        i+=1

if N==1:
    print(1)
else:
    for i in range(0,N):
        if S[i]=='o':
            if i==0:
                if K>data2[N-2]:
                    print(i+1)
            elif N-1>i:
                work,nextday=data1[i-1]
                if nextday!=N:
                    nextday=max(nextday,i+1)
                    if K>work+data2[N-1-nextday]:
                        print(i+1)
                else:
                    if K>work:
                        print(i+1)
            elif i==N-1:
                if K>data1[N-2][0]:
                    print(i+1)
n,m=map(int,input().split())

if n>m:
  print(n+n-1)
  
elif n<b:
  print(m+m-1)

  else:
  print(n+m)

### FIXED CODE ###

a,b=map(int,input().split())
if a>b:
  print(a+a-1)
elif a<b:
  print(b+b-1)
else:
  print(a+b)
dict = {ch: list(input()) for ch in "abc"}
ch = "a"

While (dict[ch]):
    ch = dict[ch].pop(0)

print(ch.upper())

### FIXED CODE ###

S = {i:list(input()) for i in "abc"}
s = "a"
while S[s]:
    s = S[s].pop(0)
print(s.upper())
a=input()
if a=="MON":
  print("6")
elif a=="SUN":
  ptint("7")
elif a=="TUE":
  print("5")
elif a=="WED":
  print("4")
elif a=="THU":
  print("3")
elif a=="FRI":
  print("2")
else:
  print("1")


### FIXED CODE ###

a=input()
if a=="MON":
  print("6")
elif a=="SUN":
  print("7")
elif a=="TUE":
  print("5")
elif a=="WED":
  print("4")
elif a=="THU":
  print("3")
elif a=="FRI":
  print("2")
elif a=="SAT":
  print("1")
n=int(input())
*a=map(int,input().split())

for i in range(n):
	v=a[i]
	j=i-1
	while j>=0 and a[j]>v:
		a[j+1]=a[j]
		j-=1
	a[j+1]=v

	print(*a)



### FIXED CODE ###

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

for i in range(n):
	v=a[i]
	j=i-1
	while j>=0 and a[j]>v:
		a[j+1]=a[j]
		j-=1
	a[j+1]=v

	print(*a)
def function():
    N,M = map(int, input().split())
    paths = []
    for _m in range(M+1):
        paths.append([])    
    
    for _m in range(M):
        A,B = map(int, input().split())
        paths[A].append(B)
        paths[B].append(A)
    
    dist = [-1]*(N+1)
    dist[1] = 0
    pre = [-1]*(N+1)
    q = [1] # 1からスタート
    while len(q) != 0:
        i = q.pop(0)
        for ne in paths[i]:
            if dist[ne] == -1:
                dist[ne] = dist[i]+1
                pre[ne] = i
                q.append(ne)
    #print(dist)
    print('Yes')
    pre.pop(0)
    pre.pop(0)
    for d in pre:
        print(d)

if __name__ == '__main__':
    function()


### FIXED CODE ###

def function():
    N,M = map(int, input().split())
    paths = []
    for _ in range(N+1):
        paths.append([])
    
    for _m in range(M):
        A,B = map(int, input().split())
        paths[A].append(B)
        paths[B].append(A)
    
    dist = [-1]*(N+1)
    dist[1] = 0
    pre = [-1]*(N+1)
    q = [1] # 1からスタート
    while len(q) != 0:
        i = q.pop(0)
        for ne in paths[i]:
            if dist[ne] == -1:
                dist[ne] = dist[i]+1
                pre[ne] = i
                q.append(ne)
    #print(dist)
    print('Yes')
    pre.pop(0)
    pre.pop(0)
    for d in pre:
        print(d)

if __name__ == '__main__':
    function()
a,b=map(int,input().split())
num=0
nums=[]
for i in range(1,1000):
    num+=i
    nums.append(num)
for i in range(1,999):
    if nums[i]-a==num[i+1]-b:
        print(nums[i])


### FIXED CODE ###

a,b=map(int,input().split())
num=0
nums=[]
for i in range(1,1000):
    num+=i
    nums.append(num)
for i in range(998):
    if nums[i]-a==nums[i+1]-b:
        print(nums[i]-a)
from functools import reduce
from fractions import gcd

A, B, C, D = map(int, input().split())
X = math.gcd(C, D)*C*D
print(X)

N = B-A+1
print(N-(N//C+N//D-N//X))

### FIXED CODE ###

from functools import reduce
from fractions import gcd

A, B, C, D = map(int, input().split())
X = C//gcd(C, D)*(D//gcd(C, D))*gcd(C, D)

print(B-A-(B//C-(-(-A//C))+B//D-(-(-A//D))-(B//X-(-(-A//X)))))
A, B= map(int, input().split())
C = int(input())

A_B = (A*B) % 2

if A_B == 0:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

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

A_B = (A*B) % 2

if A_B == 0:
    print("No")
else:
    print("Yes")
X, Y, A, B, C = map(int,input().split())
P = [int(_) for _ in input().split()]
Q = [int(_) for _ in input().split()]
R = [int(_) for _ in input().split()]

P.sort()
Q.sort()
R.sort()
R.reverse()

P = P[A-X:]
Q = Q[B-Y:]

i = 0
j = 0

while min(P[i],Q[j])<R[i+j] and i+j<C:
    if P[i] < Q[j]:
        i += 1
    else:
        j += 1
    if i+j == C:
        break

ans = 0
for e in P[i:]:
    ans = ans + e
for e in Q[j:]:
    ans = ans + e
for a in range(i+j):
    ans = ans + R[a]

print(ans)

### FIXED CODE ###

X, Y, A, B, C = map(int,input().split())
P = [int(_) for _ in input().split()]
Q = [int(_) for _ in input().split()]
R = [int(_) for _ in input().split()]

P.sort()
Q.sort()
R.sort()
R.reverse()

P = P[A-X:]
Q = Q[B-Y:]

P.append(10**9+1)
Q.append(10**9+1)
R.append(0)


i = 0
j = 0


while min(P[i],Q[j])<R[i+j]:
    if P[i] < Q[j]:
        i += 1
    else:
        j += 1
    if i+j == C:
        break

P.remove(10**9+1)
Q.remove(10**9+1)
R.remove(0)

ans = 0
for e in P[i:]:
    ans = ans + e
for e in Q[j:]:
    ans = ans + e
for a in range(i+j):
    ans = ans + R[a]

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

if S.count(5) == 2 && S.count(7):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

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

if S.count(5) == 2 and S.count(7):
  print("YES")
else:
  print("NO")
strings = list(input())
alfabet  = 'abcdefghijklmnopqrstuvwxyz'
for i in alfabet:
    if strings.count(i) <= 1:
        result = i
        break

print(result)

### FIXED CODE ###

strings = list(input())
alfabet  = 'abcdefghijklmnopqrstuvwxyz'

for i in alfabet:
    if strings.count(i) == 0:
        result = i
        break
else:
    result = "None"

print(result)
N=int(input())
Ds=list(map(int,input().split()))

if min(Ds)!=0 or Ds.count(0)!=1:
    print(0)
else:
    Ans=[0]*(max(Ds)+1)
    Ans[0]=1
    for i in range(1, max(Ds)+1):
        Ans[i]=(Ans[i-1]*(Ds.count(i-1)**Ds.count(i)))

    print(Ans[max(Ds)])%998244353

### FIXED CODE ###

n=int(input())
if n%2==0:
    Ans=n//2-1
else:
    Ans=n//2
print(Ans)
from math import gcd
lcm = lambda x, y: x*y//gcd(x, y)

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr = [e//2 for e in arr]

cm = arr[0]
for e in arr[1:]:
    cm = lcm(cm, e)

if any([cm//e % 2 == 0 for e in arr]):
    print(0)
    exit()
print((m//cm+1)//2)


### FIXED CODE ###

def gcd(x, y):
    if x == 0: return y
    return gcd(y%x, x)
lcm = lambda x, y: x*y//gcd(x, y)

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr = [e//2 for e in arr]

cm = arr[0]
for e in arr[1:]:
    cm = lcm(cm, e)

if any([cm//e % 2 == 0 for e in arr]):
    print(0)
    exit()
print((m//cm+1)//2)
n,k=map(int,input().split())
P=[list(map(int,input().split())) for _ in range(n)]
X=sorted(list(map(lambda x:x[0],P)))
Y=sorted(list(map(lambda x:x[1],P)))
s=(X[0]-X[-1])*(Y[0]-Y[-1])
ans=0
for r in range(1,n):
  for l in range(r):
    if c<k:
      break
    for u in range(1,n):
      for b in range(u):
        c=0
        for p in P:
          if X[l]<=p[0]<=X[r] and Y[b]<=p[1]<=Y[u]:
            c+=1
        if c>=k:
          s=min(s,(X[r]-X[l])*(Y[u]-Y[b]))
        else:break
print(s)

### FIXED CODE ###

n,k=map(int,input().split())
P=[list(map(int,input().split())) for _ in range(n)]
X=sorted(list(map(lambda x:x[0],P)))
Y=sorted(list(map(lambda x:x[1],P)))
s=(X[0]-X[-1])*(Y[0]-Y[-1])
ans=0
for r in range(n-1,0,-1):
  for l in range(r):
    for u in range(n-1,0,-1):
      for b in range(u):
        c=0
        for p in P:
          if X[l]<=p[0]<=X[r] and Y[b]<=p[1]<=Y[u]:
            c+=1
        if c>=k:
          s=min(s,(X[r]-X[l])*(Y[u]-Y[b]))
        else:break
    if u==n-1 and b==0 and c<k:
      break
print(s)
N, M = map(int, input().split())
A = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(M)]
A = sorted(A)
bc = sorted(bc, reverse=True, key=lambda x:x[1])
i = 0
for b, c in bc:
    while A[i] <= c and b > 0:
        A[i] = c
        b -= 1
        i += 1
        if i >= N:
            break
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(M)]
A = sorted(A)
bc = sorted(bc, reverse=True, key=lambda x:x[1])
i = 0
for b, c in bc:
    while A[i] <= c and b > 0:
        A[i] = c
        b -= 1
        i += 1
        if i >= N:
            break
    if i >= N:
        break
print(sum(A))
N,M=map(int,input().split())
*A,=map(int,input().split())
A=sorted(A)[::-1]
count=0
now=0
while M:
    i=0
    while i<=now and M:
        if count<N-1:
            while A[i]<A[count+1]:
                A[count+1]//=2
                count+=1
                M-=1
                if M==0:
                    break
        if M==0:
            break
        A[i]//=2
        i+=1
        M-=1
    now=count
        
print(sum(A))

### FIXED CODE ###

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

while M:
    A[-1]//=2
    M-=1
    i=-2
    while M and (-N<=i and A[i]>=A[-1]):
        A[i]//=2
        M-=1
        i-=1
    A.sort()

print(sum(A))
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):
    b = B[i]
    a = bisect.bisect_left(A,b)
    c = bisect.bisect_right(C,b)
    ans+=(a*(len(C)-c))
print(ans)

### FIXED CODE ###

import bisect

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

ans = 0
for i in range(N):
    b = B[i]
    a = bisect.bisect_left(A,b)
    c = bisect.bisect_right(C,b)
    ans+=(a*(len(C)-c))
print(ans)
N, K = map(int, input().split())
if K % 2:
    print((N // K) ** 3)
else:
    print((N // K) ** 3 + ((N + K // 2) // K) ** 3)

### FIXED CODE ###

A,B,C,X=[int(input())for _ in[0]*4]
ans=sum(a*500+b*100+c*50==X for a in range(A+1)for b in range(B+1)for c in range(C+1))
print(ans)
n=int(input())
a=list(map(int,input().split()))
count=0
countk=0
saidaiti=0
while True:
    saidaiti=saidaiti+abs(a[count])
    count=count+1
    if a[count]%2==1:
        countk=countk+1
    if count==n:
        break
if countk%2==1:
    saidaiti=saidaiti-2*a[-1]
print(saidaiti)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[abs(i) for i in a]
print(sum(b)-sum(i<0 for i in a)%2*min(b)*2)
def bellman_ford(n, edges, s):
    d = [float('inf')] * n
    d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        
        if not update or loop_cnt >= n: break
    return d, (loop_cnt >= n)

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a-1, b-1, -c))

dist, cycle = bellman_ford(n, edges, 0)
if cycle:
    print("inf")
else :
    print(dist[n])

### FIXED CODE ###

def bellman_ford(n, edges, s, distance=None):
    if distance != None:
        d = distance[:]
    else :
        d = [float('inf')] * n
        d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True

        if not update or loop_cnt > n: break
    return d

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a-1, b-1, -c))

dist = bellman_ford(n, edges, 0)
test = bellman_ford(n, edges, 0, dist)

if dist[n-1] != test[n-1]:
    print("inf")
else :
    print(-dist[n-1])
import math
n=int(input())
x=list(map(int,input().split()))
l=min(x)
r=max(x)
cost=[]
for i in range(l,r):
    curcost=0
    for j in range(n):
        curcost+=(x[j]-i)**2
    cost.append(curcost)
print(min(cost))

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
l=min(x)
r=max(x)
cost=[]
for i in range(l,r+1):
    curcost=0
    for j in range(n):
        curcost+=(x[j]-i)**2
    cost.append(curcost)
print(min(cost))
#"""
import sys
input = sys.stdin.readline
#"""

N=int(input())
A = [list(map(int,input().split())) for _ in [0]*N]

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    k1 = (i,B[0]-1)
    for j in range(N-2):
        a1 = B[j+1]-1
        k0 = k1
        k1 = (i,a1) if i<a1 else (a1,i)
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

### FIXED CODE ###

#"""
import sys
input = sys.stdin.readline
#"""
def main():
    def get_key(i,j):
        if i<j: i,j = j,i
        return i*N+j
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]
    V = [-1]*(N*N)
    for i in range(N):
        for j in range(i+1,N):
            V[get_key(i,j)] = 0
    Ef = [[] for _ in V]

    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1)
            Ef[get_key(*k0)].append(get_key(*k1))
            V[get_key(*k1)] += 1

    q = [i for i,v in enumerate(V) if v == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for i in q:
            for j in Ef[i]:
                V[j] -= 1
                rmv += 1
                if V[j] == 0 : qq.append(j)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()
x = raw_input().split()
y = map(int, x)
a = y[0]
b = y[1]
c = a*b
d = (a+b)*2
print c, d

### FIXED CODE ###

x = raw_input().split()
y = map(int, x)
a = y[0]
b = y[1]
c = a*b
d = (a+b)*2
print c, d
N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N-1)]
m=10**9+7
c=[[] for i in range(N)]
for i,j in A:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
def bfs(p):
    r=K
    d=1
    n=[1]*N
    while len(p)>0:
        q=[]
        for e in p:
            n[e]=0
            x=max(K-min(2,d),0)
            for f in c[e]:
                if n[f]:
                    q.append(f)
                    r=(r*x)%m
                    x-=1
        p=q
        d+=1
    return r
print(bfs([A[0][0]-1]))

### FIXED CODE ###

N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N-1)]
m=10**9+7
c=[[] for i in range(N)]
for i,j in A:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
import sys
sys.setrecursionlimit(10**6)
def bfs(p):
    r=K
    d=1
    n=[1]*N
    while len(p)>0:
        q=[]
        for e in p:
            n[e]=0
            x=max(K-min(2,d),0)
            for f in c[e]:
                if n[f]:
                    q.append(f)
                    r=(r*x)%m
                    x-=1
        p=q
        d+=1
    return r
print(bfs([A[0][0]-1]) if N>1 else K)
import sys
d={"Vacant":0, "Male":1, "Female":-1}

N=int(input())
M=[2 for _ in range(N+1)]
print(0, flush=True)
M[0]=d[input()]
M[N]=M[0]

def search(l,r):
    if r - l == 2:
        print(l+1)
        sys.exit()
    print((l+r)//2,flush=True)
    return d[input()]
l=0
r=N
while True:
    M[(r+l)//2] = search(l,r)
    if M[(r+l)//2] != M[l]:
            r=(r+l)//2
    elif M[(r+l)//2] != M[r]:
            l=(r+l)//2
    else:
        print("something wrong")

### FIXED CODE ###

import sys
d={"Vacant":0, "Male":1, "Female":-1}

N=int(input())
M=[2 for _ in range(N+1)]
print(0, flush=True)
M[0]=d[input()]
M[N]=M[0]

def search(l,r):
    if r - l == 2:
        print(l+1)
        sys.exit()
    print((l+r)//2, flush=True)
    return d[input()]
l=0
r=N
while True:
    m=(r+l)//2
    M[m] = search(l,r)
    if M[m] == 0:
        print(m)
        sys.exit()
    if (m-l) % 2 == 0:
        if M[m] == M[l]:
            l=m
        else:
            r=m
    else:
        if M[m] == M[l]:
            r=m
        else:
            l=m
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

int gcd(int x,int y){
  if(x<y) swap(x,y);
  //xの方が常に大きい
  while(y>0){
    int r=x%y;
    x=y;
    y=r;
  }
  return x;
}

int lcm(int x,int y){
  return int(x*y/gcd(x,y));
}

//n個の場合のlcmも2個で比べて順に適用していくだけ
int main(){
  int n,m;cin >> n >> m;
  vector<int> a(n);for(int i=0;i<n;i++){cin >> a[i];a[i]/=2;}
  int ans=lcm(a[0],a[1]);
  for(int i=1;i<n;i++){ans=lcm(ans,a[i]);}
  //cout << ans << endl;
  cout << int((floor(m/ans)+1)/2) << endl;
}


### FIXED CODE ###

from math import gcd
def lcm(a,b):
    return a//gcd(a,b)*b
def lcm(ab):
    l=len(ab)
    ret=ab[0]
    for i in range(1,l):
        ret=ret//gcd(ab[i],ret)*ab[i]
    return ret
def count2(a):
    ret=0
    while a%2==0:
        a//=2
        ret+=1
    return 2**ret
n,m=map(int,input().split())
A=list(map(int,input().split()))
if any(i%2 for i in A):
    exit(print(0))
A=[i//2 for i in A]
#全体の最小公倍数
p=lcm(A)
c=count2(p)
#2で割り切れる回数が同じでないものがある場合
#違うじゃん
if any(i%c for i in A):
    exit(print(0))
x=m//p
#print(p//c)
if x%2==0:
    print(x//2)
else:
    print(x//2+1)
n = int(input())
for i in range(1,10):
    t = 10-i
    if n > t*100 + t*10 + t:
        res = (t+1)*100 + (t+1)*10 + t+1
        break

print(res)


### FIXED CODE ###

n = int(input())
for t in range(1,10):
    if n <= t*100 + t*10 + t:
        res = t*100 + t*10 + t
        break 

print(res)