Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n-1):
  a[i+1]*=a[i]
print(a[i+1] if a[i+1]<=10**18 else -1)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
  s *= a[i]
  if s>10**18:
      print(-1)
      exit()
print(s)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
h = list(map(int, input().split()))
d = np.inf
dp = [d] * N
dp[0] = 0
cc = np.arange(1, N)
for i in cc:
  c =  np.arange(1, min(i, K)+1)
  min1 = min([dp[i-j]+np.abs(h[i]-h[i-j]) for j in c])
  dp[i] = min1
print(dp[N-1])

### FIXED CODE ###

import sys
import numpy as np

# inputを高速化する。
input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# dpの配列を作る。
dp = np.zeros(n, dtype=int)
# hの配列を作る。
h = np.array(h)


for i in range(1, n):
    # start は負になることはない。
    start = max(0, i-k)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

N = int(input())
cn = input()
sto = list(cn)
count = 0

r = sto.count("R")
for i in range(r):
    if sto[i] == "W":
        sto[i] = "R"
        for j in range(r,N):
            if sto[j] == "R":
                sto[j] = "W"
                count += 1
print(count)


### FIXED CODE ###

N = int(input())
cn = input()
sto = list(cn)
count = 0

r = sto.count("R")
for i in range(r):
    if sto[i] == "W":
      count += 1
print(count)
### BUGGY CODE ###

from collections import Counter
import sys


def main():
    sys.setrecursionlimit(10**7)
    readline = sys.stdin.buffer.readline
    N = int(readline())
    A = list(map(int, readline().split()))
    C = Counter(A)

    l, m, n = C[3], C[2], C[1]
    dp = [[[0]*(l+m+n+1) for _ in range(l+m+1)] for _ in range(l+1)]
    seen = [[[False]*(l+m+n+1) for _ in range(l+m+1)] for _ in range(l+1)]
    seen[0][0][0] = True

    def exval(i, j, k):
        if seen[i][j][k]:
            return dp[i][j][k]
        s = N
        if i > 0:
            s += i*exval(i-1, j+1, k)
        if j > 0:
            s += j*exval(i, j-1, k+1)
        if k > 0:
            s += k*exval(i, j, k-1)
        dp[i][j][k] = s / (i+j+k)
        seen[i][j][k] = True
        return dp[i][j][k]


    print(exval(l, m, n))


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter
import sys


def main():
    sys.setrecursionlimit(10**6)
    readline = sys.stdin.buffer.readline
    N = int(readline())
    A = list(map(int, readline().split()))
    C = Counter(A)

    l, m, n = C[3], C[2], C[1]
    dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = 0

    def exval(i, j, k):
        if dp[i][j][k]!=-1:
            return dp[i][j][k]
        s = N
        if i > 0:
            s += i*exval(i-1, j+1, k)
        if j > 0:
            s += j*exval(i, j-1, k+1)
        if k > 0:
            s += k*exval(i, j, k-1)
        dp[i][j][k] = s / (i+j+k)
        return dp[i][j][k]


    print(exval(l, m, n))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

S = input()
N = len(S)
P = 2019

A = [0] * (N+1)
for i in range(N):
    A[i+1] = (A[i] + int(S[N-1 - i]) * (10**i)) % P

c = collections.Counter(A)
ans = 0
for k, v in c.items():
    ans += v * (v-1) // 2

print(ans)


### FIXED CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

S = input()
N = len(S)
P = 2019

A = [0] * (N+1)
for i in range(N):
    A[i+1] = (A[i] + int(S[N-1 - i]) * pow(10, i, P)) % P

c = collections.Counter(A)
ans = 0
for v in c.values():
    ans += v * (v-1) // 2

print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
s=input()
for _ in range(Q):
    l,r=map(int,input().split())
    print(s[l-1:r].count('AC'))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
l=[0]*(len(s)+1)
for i in range(1,len(s)):
    l[i+1]=l[i]
    if s[i-1]=='A' and s[i]=='C':
        l[i+1]+=1
ans=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    ans[i]=l[b]-l[a]
print(*ans,sep='\n')
### BUGGY CODE ###

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

mod = 10 ** 9 + 7

S = 0
for x in range(N):
    for y in range(1, N - x, 1):
        S = (S + A[x] * A[x + y]) % mod

print(S)


### FIXED CODE ###

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

mod = 10 ** 9 + 7

sumA = sum(A)
S = 0

for x in range(N):
    sumA -= A[x]
    S = (S + A[x] * (sumA)) % mod

print(S)
### BUGGY CODE ###

from sys import stdout
import random

def query(num):
    print(num)
    stdout.flush()
    return input()

N = int(input())
first_query = query(0)
if first_query == "Vacant":
    print(0)

else:
    candidate = [i for i in range(2, N)][0::2]
    while True:
        idx　= random.choice(range(len(candidate)))
        candidate.pop(idx)
        q = query(candidate[idx]) 
        if q == "Vacant":
            print(candidate[idx])
            break
        elif q != first_query:
            cand = (candidate[idx] - 1) % N
            if query(cand) == "Vacant":
                print(cand)
            else:
                print((candidate[idx] + 1) % N)
            break

### FIXED CODE ###

N = int(input())
 
def query(x):
    print(x, flush=True)
    response = input()
    if response == "Vacant":
        exit()
    return response
 
lb = 0
ub = N - 1

l_query = query(lb)
u_query = query(ub)

while True:
    m = (lb + ub) // 2
    m_query = query(m)
    if (m_query == l_query) == (m % 2 == lb % 2):
        lb = m
        l_query = m_query
    else:
        ub = m
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
 
for i in range(Q):
    B, C = map(int, input().split())
 
    A = [C if i == B else i for i in A]
 
    print(sum(A))

### FIXED CODE ###

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

data = [0] * 100001

def my_sum(d):
    retval = 0

    for i in range(len(d)):
        if d[i] == 0:
            continue
        retval += d[i] * i
    return retval

for i in A:
    data[i] += 1

sum_val = my_sum(data)

for i in range(Q):
    B, C = map(int,input().split())

    sum_val = sum_val - (data[B] * B) + (data[B] * C)

    data[C] += data[B]
    data[B] = 0

    print(sum_val)
### BUGGY CODE ###

a, b = map(int, input().split())
c = min(a, b)
for i in range(c, a * b + 1):
    if i % a == 0 and i % b == 0:
        print(i)
        exit()

### FIXED CODE ###

a, b = map(int, input().split())
c = a * b
d = min(a, b)
j = 1
for i in range(2, d + 1):
    j += 1
    if a % j == 0 and b % j == 0:
        c //= j
        a //= j
        b //= j
        j = 1
print(c)
### BUGGY CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: -x[0])

    ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        # bisect.insort_left(ind_list, ori_ind)
        # add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        ind_list.insert(add_ind, ori_ind)
        # print(add_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: x[0])

    left = [0, 0] + [i + 1 for i in range(num)]
    right = [i + 1 for i in range(num)] + [num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        l1 = left[ori_ind]
        l2 = left[l1]
        r1 = right[ori_ind]
        r2 = right[r1]

        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

        right[l1] = r1
        left[r1] = l1

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import itertools as ite
import math
import random
import sys
import codecs
from collections import defaultdict

INF = 10 ** 18
MOD = 10 ** 9 + 7

sys.setrecursionlimit(1000000)

N = input()
A = [input() for i in range(N)]
maxA = max(A)
if A.count(maxA) > 1:
    for i in range(N):
        print maxA
else:
    for i in range(N):
        if A[i] == maxA:
            print max(A[:i] + A[i + 1:])
        else:
            print max(A)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import itertools as ite
import math
import random
import sys
import codecs
from collections import defaultdict

INF = 10 ** 18
MOD = 10 ** 9 + 7

sys.setrecursionlimit(1000000)

N = input()
A = [input() for i in range(N)]
maxA = max(A)
if A.count(maxA) > 1:
    for i in range(N):
        print maxA
else:
    for i in range(N):
        if A[i] == maxA:
            print max(A[:i] + A[i + 1:])
        else:
            print maxA
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N-1):
    while A[i] > A[i+1]:
        A[i + 1] += 1
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(1,N):
    if A[i-1] > A[i]:
        count += A[i-1] - A[i]
        A[i] = A[i - 1]
print(count)
### BUGGY CODE ###

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

leq,high = 0,10**19
while high-leq > 1:
  l = (leq+high)//2
  cnt = 0
  for ai in a:
    cnt += int((ai-1)/l)
  if cnt>k:
    leq = l
  else:
    high = l

print(high)


### FIXED CODE ###

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

# 合計N+Kこになる


l = 0
r = 2 * 10 ** 9 + 10 ** 6
while r - l > 1:
    m = (r + l) // 2
    cnt = 0
    for a in A:
        cnt += (a + m - 1) // m
    if cnt <= N + K:
        r = m
    else:
        l = m

print(r)
### BUGGY CODE ###

import collections
n = int(input())
ls = []
for i in range(n):
    s = input()
    ls.append(s)
    
c = collections.Counter(ls)

count = c.most_common()[0][1]
ans = []
for i in range(len(c)):
    if c.most_common()[i][1] == count:
        ans.append(c.most_common()[i][0])
    else:
        break
        
ans.sort()
for i in ans:
  print(i)

### FIXED CODE ###

import collections
from collections import Counter

n = int(input())
ls = [input() for i in range(n)]    
c = Counter(ls).most_common()

count = c[0][1]
ans = []

for i in range(len(c)):
    if c[i][1] == count:
        ans.append(c[i][0])
    else:
        break   
ans = sorted(ans)
for i in ans:
    print(i)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, K = inm()
A = inl()


def solve():
    p = 1
    for i in range(K):
        p *= A[i]
    for i in range(K, N):
        if A[i] > A[i - K]:
            print("Yes")
        else:
            print("No")


solve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, K = inm()
A = inl()


def solve():
    for i in range(K, N):
        if A[i] > A[i - K]:
            print("Yes")
        else:
            print("No")


solve()
### BUGGY CODE ###


s = input()
q = int(input())
L = []
for i in range(q):
    L.append(list(input().split()))
    if L[-1][0] == '1' :
        s = ''.join(reversed(s))
    if L[-1][0] == '2' :
        if L[-1][1] == '1' :
            s = L[-1][2] + s
        if L[-1][1] == '2' :
            s = s + L[-1][2]
print(s)
        

### FIXED CODE ###


from collections import deque

s = deque(list(input()))
q = int(input())
head = 0

for i in range(q):
    L = list(input().split())
    if L[0] == '1' :
        head = (head + 1)%2
    if L[0] == '2' :
        if head == 0:
            if L[1] == '1' :
                s.appendleft(L[2])
            if L[1] == '2' :
                s.append(L[2])
        if head == 1:
            if L[1] == '1' :
                s.append(L[2])
            if L[1] == '2' :
                s.appendleft(L[2])
if head == 0:
    print(''.join(s))
else: 
    print(''.join(reversed(s)))
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
total = [a.count(i)+a.count(i-1)+a.count(i+1) for i in a]
print(max(total))

### FIXED CODE ###

n = int(input())
count = [0] * 100002
a = list(map(int, input().split()))
for i in a:
    count[i-1] += 1
    count[i] += 1
    count[i+1] += 1

print(max(count))
### BUGGY CODE ###

x1 = input()
x2 = [int(s) for s in input().split(" ") ]

if len(x2) >0 :
  result =  1
else :
  result =  0
for x in x2:
  result *= x 

if 10**18 < result :
  print (-1)
else:
  print (result)

### FIXED CODE ###

x1 = input()
x2 = [int(i) for i in input().split(" ")]

result = 0
if 0 in x2:
  None 
else:
  result = 1
  for xv in x2:
     result = xv * result
  
     if 10**18 < result : 
        result = -1
        break


print(result)
### BUGGY CODE ###

N = int(input())
A = [str(_) for _ in input().split(" ")]

ans = [] 
for i in range(N):
    ans.append(str(A.index(str(i + 1)) + 1))

print(" ".join(ans))

### FIXED CODE ###

import numpy as np

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

ans = np.argsort(A)

for i in range(N):
    print(ans[i] + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
MOD = 10**9+7

n, m = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
  for j in range(m+1):
    if i == 0 or j == 0:
      dp[i][j] = 1
    else:
      dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
      if S[i-1] == T[j-1]:
        dp[i][j] += dp[i-1][j-1]
      dp[i][j] %= MOD
ans = dp[n][m]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
MOD = 10**9+7

n, m = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
  for j in range(m+1):
    if i == 0 or j == 0:
      dp[i][j] = 1
    else:
      dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
      if S[i-1] == T[j-1]:
        dp[i][j] += dp[i-1][j-1]
      dp[i][j] %= MOD
ans = dp[n][m]
print(ans)
### BUGGY CODE ###

###C - Monsters Battle Royale
N = int(input())
A = list(map(int, input().split()))
jlist=[True]
cnt = 0
while(min(A) !=1 and len(set(A)) != 1):
    cnt = 0
    for i in range(N):
        if A[i] - min(A) > 0:
            A[i] = A[i] - min(A)
print(min(A))

### FIXED CODE ###

###C - Monsters Battle Royale
N = int(input())
A = list(map(int, input().split()))

while(len(set(A)) != 1):
    minA  = min(A)
    for i in range(N):
        if A[i] > minA:
            time = A[i] // minA
            if time == 1:
                A[i] =A[i] -  time * minA
            else:
                A[i] =A[i] -  (time - 1) * minA
                
print(min(A))
### BUGGY CODE ###

s=input()

d=[0]*2019
dp=0
d[0]+=1
l=len(s)
r=1

for i in range(l-1,-1,-1):
	dp+=int(s[i])*r
	dp%=2019
	r*=10%2019
	d[dp]+=1

res=0

for a in d:
	res+=a*(a-1)//2
	
print(res)

### FIXED CODE ###

s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

for i in range(2019):
    cnt += int(countRemainder[i] * (countRemainder[i] - 1) / 2)

print(cnt)
### BUGGY CODE ###


k,s = map(int,input().split())
a,b,c = 0,0,0
count= 0

for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i + j + l == s:
                count += 1
print(count)


### FIXED CODE ###

k,s = map(int,input().split())
count = 0
for i in range(k+1):
  for m in range(k+1):
    if 0 <= s-i-m <= k:
      count += 1
print(count)
### BUGGY CODE ###

X = int(input())

B = 0
Bp = 0
Bm = 0
while True:
    A = (X + Bp ** 5) ** 0.2
    if not isinstance(A, complex):
        if A.is_integer():
            B = Bp
            break
    Bp += 1

    A = (X + Bm ** 5) ** 0.2
    if not isinstance(A, complex):
        if A.is_integer():
            B = Bm
            break
    Bm -= 1


print(str(int(A)) + " " + str(B))


### FIXED CODE ###

X = int(input())

for a in range(-300, 300):
    for b in range(-300, 300):
        if a ** 5 - b ** 5 == X:
            A = a
            B = b

print(str(A) + " " + str(B))
### BUGGY CODE ###

from itertools import accumulate as ac
n,k=map(int,input().split())
*l,=map(int,input().split())
*m,=map(lambda x:max(x,0),l)
*acc,=ac([0]+l)
v=0
for i in range(n-k+1):
  v=max(v,max(0,acc[i+k]-acc[i])+sum(m[i+k:])+sum(m[:i]))
print(v)

### FIXED CODE ###

from itertools import accumulate as ac
n,k=map(int,input().split())
*l,=map(int,input().split())
*m,=map(lambda x:max(x,0),l)
*acc,=ac([0]+l)
*acm,=ac([0]+m)
v=0
for i in range(n-k+1):
  v=max(v,max(0,acc[i+k]-acc[i])+acm[n]-acm[i+k]+acm[i])
print(v)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline

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

    result = list()

    for i in range(N):
        Pj = list(P[j] for j in range(i+1))
        #print(Pj)
        #Pj = P[0:i+1]
        min_P = min(Pj)
        result.append(min_P)
#        print(min_P)
#        if(P[i] == min_P):
#            count += 1

    print(len(set(result)))

    '''
    count = 0
    flag = True

    for i in range(N):
        for j in range(i):
            if(P[i] > P[j]):
                flag = False
                break
        if(flag):
            count += 1
        flag = True
    print(count)
    '''

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

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

    #result = list()

    minimum = P[0]
    count = 1
    for i in range(N):
        if(minimum > P[i]):
            minimum = P[i]
            count += 1
    print(count)
#        Pj = list(P[j] for j in range(i+1))
        #print(Pj)
        #Pj = P[0:i+1]
#        min_P = min(Pj)
#        result.append(min_P)
#        print(min_P)
#        if(P[i] == min_P):
#            count += 1

    '''
    count = 0
    flag = True

    for i in range(N):
        for j in range(i):
            if(P[i] > P[j]):
                flag = False
                break
        if(flag):
            count += 1
        flag = True
    print(count)
    '''

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)


N, M = map(int, input().split())
to = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int, input().split())
    to[x - 1].append(y - 1)


count = 0
def dfs(v, seen, temp=0):
    global count
    seen[v] = 1
    if to[v]:
        for nv in to[v]:
            dfs(nv, seen, temp + 1)
    else:
        count = max(count, temp)


def main():
    ans = 0
    seen = [0] * N
    for i in range(N):
        if not seen[i]:
            dfs(i, seen)
            ans = max(ans, count)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)


N, M = map(int, input().split())
to = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int, input().split())
    to[x - 1].append(y - 1)

# dp[i] : iを始点とする最長経路
dp = [0] * N
seen = [0] * N

def dfs(v):
    if seen[v]:
        return dp[v]
    seen[v] = 1
    res = 0
    for nv in to[v]:
        res = max(res, dfs(nv) + 1)
    dp[v] = res
    return res


def main():
    ans = 0
    for i in range(N):
        ans = max(ans, dfs(i))
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    u-=1
    v-=1
    while u!=v:
        if u>v:
            u=(u-1)//n
        else:
            v=(v-1)//n
    print(u+1)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    if n==1:
        print(min(u,v))
        continue
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(((u-1)//n)-1)//n
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(((v-1)//n)-1)//n
            else:
                v=(v-1)//n
    print(u+1)
### BUGGY CODE ###

from collections import defaultdict
s=input().strip()
t=input().strip()


def gg(cc, c, l, d):
    if d[c][-1] <= cc:
        return d[c][1], l+1
    ll = d[c]
    mx, mn = len(ll)-1, 0
    x = (mx - mn)//2
    while True:
        if ll[x] <= cc and cc < ll[x+1]:
            return ll[x+1], l
        if cc < ll[x]:
            mx = x
            x = (mx-mn)//2
        else:
            mn = x
            x = (mx-mn)//2

def main():
    ss=set(s)
    tt=set(t)
    if len(tt - ss) != 0: 
        return -1
    d = dict()
    for i, c in enumerate(s):
        if c not in d:
            d[c] = [0]
        d[c].append(i+1)
    cc, l = 0, 0
    for c in t:
        cc, l = gg(cc, c, l, d)
    return l*len(s) + cc

if __name__ == '__main__':
    print(main())



### FIXED CODE ###

from collections import defaultdict
s=input().strip()
t=input().strip()
def gg(cc, c, l, d):
    if d[c][-1] <= cc:
        return d[c][1], l+1
    ll = d[c]
    mx, mn = len(ll)-1, 0
    x = (mx + mn)//2
    while True:
#        print(x,cc,mx,mn,ll)
        if ll[x] <= cc and cc < ll[x+1]:
            return ll[x+1], l
        if cc < ll[x]:
            mx = x
            x = (mx+mn)//2
        else:
            mn = x
            x = (mx+mn)//2

def main():
    ss=set(s)
    tt=set(t)
    if len(tt - ss) != 0: 
        return -1
    d = dict()
    for i, c in enumerate(s):
        if c not in d:
            d[c] = [0]
        d[c].append(i+1)
    cc, l = 0, 0
    for c in t:
#        print(c)
        cc, l = gg(cc, c, l, d)
    return l*len(s) + cc

if __name__ == '__main__':
    print(main())