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

from math import gcd, sqrt
from functools import reduce
def sieve(n):
    if n <= 4:
        return list(range(2, n))
    def _sieve_of_eratosthenes(n):
        table = [1] * n
        table[0] = table[1] = 0
        for i in range(2, int(sqrt(n))+1):
            if table[i]:
                for j in range(i**2, n, i):
                    table[j] = 0
        return [i for i in range(2, n) if table[i]]
    return _sieve_of_eratosthenes(n)

n, *A = map(int, open(0).read().split())
P = sieve(max(A))

def f(A, P):
    D = set()
    for a in A:
        for p in P:
            if a % p == 0:
                if p not in D:
                    D.add(p)
                    a //= p
                else:
                    return False
    return True

if reduce(gcd, A) == 1:
    if f(A, P):
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from math import gcd, sqrt
from functools import reduce

n, *A = map(int, open(0).read().split())
def f(A):
    sup = max(A)+1
    table = [set() for i in range(sup)]
    for i in range(2, sup):
        if not table[i]:
            for j in range(i, sup, i):
                table[j].add(i)
    D = set()
    for a in A:
        for b in table[a]:
            if b not in D:
                D.add(b)
            else:
                return False
    return True

if reduce(gcd, A) == 1:
    if f(A):
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))

maxA=max(A)

for i in range(N):
  if A[i]<maxA:
    print(maxA)
  else:
    B=A[:]
    del B[i]
    print(max(B))


### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))

maxA=max(A)
countNumber=A.count(maxA)

for i in range(N):
  if A[i]<maxA:
    print(maxA)
  elif countNumber>1:
    print(maxA)
  else:
    B=A[:]
    del B[i]
    print(max(B))
### BUGGY CODE ###

import numpy as np
from itertools import permutations


def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j, k] = min(d[j, k], d[j, i] + d[i, k])


N, M, R = map(int, input().split())
r = list(map(int, input().split()))

d = np.full((N + 1, N + 1), 1000000000, dtype=np.int64)
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A, B] = C
    d[B, A] = C
warshall_floyd(N + 1, d)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i], p[i + 1]]
    result = min(result, t)
print(result)


### FIXED CODE ###

from itertools import permutations


def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


N, M, R = map(int, input().split())
r = list(map(int, input().split()))

d = [[1000000000] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C
warshall_floyd(N + 1, d)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i]][p[i + 1]]
    result = min(result, t)
print(result)
### BUGGY CODE ###

S = input()
N = len(S)
q = []
A = 13-5
for i in range(N-1,-1,-1):
    if S[i] == '?':
        q.append(N-i-1)
    else:
        A = (A+int(S[i])*(10**(N-i-1)))%13
DP= [[0]*13 for i in range(len(q)+1)]
DP[0][A] = 1
B = [[0]*13 for i in range(13)]
for i in range(13):
    for j in range(13):
        B[i][j] = (i*j)%13
T = [1,10,9,12,3,4]
for i in range(len(q)):
    for j in range(13):
        for k in range(10):
            DP[i+1][(j+k*T[q[i]%6])%13] = (DP[i+1][(j+k*T[q[i]%6])%13]+DP[i][j])%(10**9+7)
print(DP[-1][0])

### FIXED CODE ###

S = input()
N = len(S)
DP =[0]*13
DP[0] = 1
A = 0
MOD = 10**9+7

T = [1,10,9,12,3,4]
A = 0
for i in range(N):
    A*=10
    if S[i] == "?":
        hoge = [0]*13
        for j in range(13):
            for k in range(10):
                hoge[(j+k*T[(N-i-1)%6])%13] = (hoge[(j+k*T[(N-i-1)%6])%13] + DP[j])%MOD
        DP = hoge[:]
    else:
        A += int(S[i])
    A = A%13
print(DP[(5-A)%13])
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    ans = 1
    for i in range(n):
        ans *= a[i]
    if ans >10**18:
        print(-1)
        sys.exit()
    print(ans)

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

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

import bisect
 
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0
for i in range(N):
  for j in range(i+1, N):
    min_sum = L[i]+L[j]
    more_than = bisect.bisect_left(L[j+1:], min_sum)
    ans += more_than
print(ans)


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += bisect_left(L, L[i]+L[j])-j-1
print(ans)
### BUGGY CODE ###

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

num = [0] * (len(a)+1)
for i in range(0,n):
    for j in range(len(a)):
        if a[j] == i+1:
            num[i] += 1
            if num[i] == a[j]:
                continue
    print(num[i])  

### FIXED CODE ###

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

num = [0] * n

for i in a:
    num[i-1] += 1

print(*num)
### BUGGY CODE ###

import heapq

tmp = list(map(int, input().split()))
n = tmp[0]
m = tmp[1]
a = list(map(int, input().split()))

heapq.heapify(a)

for j in range(m):
  tmp = list(map(int, input().split()))
  b = tmp[0]
  c = tmp[1]

  for k in range(b):
    if a[0] < c:
      heapq.heappop(a)
      heapq.heappush(a, c)
    else:
      break

print(sum(a))  

### FIXED CODE ###

import heapq

tmp = list(map(int, input().split()))
n = tmp[0]
m = tmp[1]
a = list(map(int, input().split()))

heapq.heapify(a)

cb = []
for j in range(m):
  tmp = list(map(int, input().split()))
  cb.append((tmp[1], tmp[0]))
cb.sort(reverse=True)

for j in range(m):
  if cb[j][0] < a[0]:
    break
  for k in range(cb[j][1]):
    if a[0] < cb[j][0]:
      heapq.heappop(a)
      heapq.heappush(a, cb[j][0])
    else:
      break

print(sum(a))
### BUGGY CODE ###

str1 = input()
str2 = input()

n = len(str1)
res = "Yes"
for i in range(n):
    for j in range(i+1,n):
        if str1[i] == str1[j]:
            if str2[i] != str2[j]:
                res = "No"
                break
        if str2[i] == str2[j]:
            if str1[i] != str1[j]:
                res = "No"
                break
    if res == "No":
        print(res)
        exit(0)

print(res)


### FIXED CODE ###

str1 = input()
str2 = input()

n = len(str1)
d1 = dict()
d2 = dict()
for i in range(26):
    d1[chr(97+i)] = ''
    d2[chr(97+i)] = ''
res = "Yes"
for i in range(n):
    if d1[str1[i]] != '' and d1[str1[i]]!=str2[i]:
        res = "No"
        break
    if d2[str2[i]] != '' and d2[str2[i]]!=str1[i]:
        res = "No"
        break
    if d1[str1[i]] == '':
        d1[str1[i]] = str2[i]
    if d2[str2[i]] == '':
        d2[str2[i]] = str1[i]
print(res)
### BUGGY CODE ###

import os, sys, re, math

r,g,b,n = input().split(' ')
r,g,b,n = int(r), int(g), int(b), int(n)

ret = 0
ri = 0
while (ri * r <= n):
    rg = 0
    while (rg * g <= n - ri * r):
        if ((n - ri *r - rg * g) % b == 0):
            ret += 1    
        rg += 1
    ri += 1

print(ret)


### FIXED CODE ###

import os, sys, re, math

r,g,b,n = input().split(' ')
r,g,b,n = int(r), int(g), int(b), int(n)

ret = 0
ri = 0
while (ri * r <= n):
    rg = 0
    while (rg * g <= n - ri * r):
        if ((n - ri * r - rg * g) % b == 0):
            ret += 1
        rg += 1
    ri += 1

print(ret)
### BUGGY CODE ###

N=int(input())
num = 7
plus = 70
i=1
if (N%2==0)or(N%5==0):
    print(-1)
else:
    while num%N!=0:
        num+=plus
        plus*=10
        i+=1
    print(i)

### FIXED CODE ###

N=int(input())
num = 7
i=1
a=[]
prir1=1
while i<=N:
    xx=num%N
    if xx==0:
        print(i)
        prir1=0
        break
    num=10*xx+7
    i+=1
if prir1:
    print(-1)
### BUGGY CODE ###

s = input()
n = len(s)

num = [0]
ans = 0

for i in range(n):
    a = int(s[-i-1:])
    a = a% 2019
    num.append(a)
    b = num[:-1]
    ans += b.count(a)

print(ans)

### FIXED CODE ###

s=input()
s=s[::-1]
n=len(s)

count=[0]*2019
count[0]=1
num,d=0,1

for i in s:
  num+=int(i)*d
  num%=2019
  d*=10
  d%=2019
  count[num]+=1

ans=0
for i in count:
  ans+=i*(i-1)//2
  
print(ans)
### BUGGY CODE ###

import numpy as np
mod = 10**9 + 7

N, K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
A = np.array(A, dtype=object)

ans = np.linalg.matrix_power(A, K).sum()
ans %= mod
print(ans)

### FIXED CODE ###

mod = 10**9 + 7

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

def dot(X, Y):
    x = len(X)
    y = len(Y[0])
    z = len(Y)
    C = [[0] * y for _ in range(x)]
    for i in range(x):
        for j in range(y):
            for k in range(z):
                C[i][j] += X[i][k] * Y[k][j]
                C[i][j] %= mod
    return C

B = [[0] * N for _ in range(N)]
for k in range(N):
    B[k][k] = 1

while K > 0:
    if K & 1:
        B = dot(B, A)
    A = dot(A, A)
    K >>= 1

ans = 0
for i in range(N):
    for j in range(N):
        ans += B[i][j]
        ans %= mod

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

import math
mod = 10**9 + 7
import sys
sys.setrecursionlimit(2147483647)
input = sys.stdin.readline

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

pat = [0 for _ in range(N+1)]
pat[0] = 1
if 1 in a :
    pat[1] = 0
else :
    pat[1] = 1

for i in range(2,N+1) :
    if i in a :
        pat[i] = 0
    else :
        pat[i] = (pat[i-1] + pat[i-2])%mod

print(pat[N])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
mod = 10**9 + 7

pat = [1 for _ in range(N+1)]
for j in a :
    pat[j] = 0

for i in range(2,N+1) :
    if pat[i] == 0 :
        continue
    else :
        pat[i] = (pat[i-1] + pat[i-2])%mod

print(pat[N])
### BUGGY CODE ###

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

cost=[-1 for _ in range(N)]


for i in range(N):
    if i==0:
        cost[i]=0
    else:
        siten=max(i-K,0)
        min_cost=10**12
        for j in range(siten,i):
            m=cost[j]+abs(h[j]-h[i])
            min_cost=min(m,min_cost)
        cost[i]=min_cost

print(int(cost[N-1]))

### FIXED CODE ###

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

cost=[-1 for _ in range(N)]


for i in range(N):
    if i==0:
        cost[i]=0
    else:
        siten=max(i-K,0)
        min_cost=10**12
        for j in range(siten,i):
            m=cost[j]+abs(h[j]-h[i])
            if m<min_cost:
                min_cost=m
        cost[i]=min_cost

print(int(cost[N-1]))
### BUGGY CODE ###

from collections import defaultdict


def calc(K, xyc):
    K2 = K * 2
    K3 = K * 3
    K4 = K * 4
    xys = [(x % K2, (y + c * K) % K2) for x, y, c in xyc]

    m = defaultdict(int)
    for x, y in xys:
        x1, y1 = x, y
        x2, y2 = (x1 + K), (y1 + K)
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x1, y2] -= 1
        m[x2, y1] -= 1

        x1, y1 = x, y + K2
        x2, y2 = (x1 + K), (y1 + K)
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x1, y2] -= 1
        m[x2, y1] -= 1

        x1, y1 = x + K2, y
        x2, y2 = (x1 + K), (y1 + K)
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x1, y2] -= 1
        m[x2, y1] -= 1

        x1, y1 = x + K2, y + K2
        x2, y2 = (x1 + K), (y1 + K)
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x1, y2] -= 1
        m[x2, y1] -= 1


    mt = defaultdict(int)
    for y in range(K4):
        for x in range(K4):
            mt[x, y] = m[x, y] + mt[(x - 1), y] + mt[x, (y - 1)] - mt[(x - 1), (y - 1)]

    rmax = 0
    for y in range(K, K3):
        for x in range(K, K3):
            rcount = mt[x + K, y + K] + mt[x, y]
            rmax = max(rmax, rcount)

    return rmax

N, K = [int(e) for e in input().split()]
xyc = [input().split() for i in range(N)]
xyc = [(int(x), int(y), c == "W") for x, y, c in xyc]

print(calc(K, xyc))


### FIXED CODE ###

def calc(K, xyc):
    K2 = K * 2
    N = len(xyc)

    p = [[0] * K2 for i in range(K2)]
    for x, y, c in xyc:
        y += c * K
        p[x % K2][y % K2] += 1
        p[(x + K) % K2][(y + K) % K2] += 1

    def isum(xs):
        r = 0
        yield r
        for x in xs:
            r += x
            yield r

    psum = [list(isum(row)) for row in p]
    pksum = [[b - a for a, b in zip(row, row[K:])] for row in psum]

    rmax = N / 2
    for y in range(K):
        rcount = sum(row[y] for row in pksum[:K])
        for x in range(K):
            rmax = max(rmax, rcount, N - rcount)
            rcount += -pksum[x][y] + pksum[x + K][y]

    return rmax

if __name__ == '__main__':
    N, K = [int(e) for e in input().split()]
    xyc = [(int(x), int(y), c == "W") for x, y, c in [input().split() for i in range(N)]]
    print(calc(K, xyc))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
l = []
for i in range(n):
    if n%2==0:
        if i%2==0:
            l.append(str(a[i]))
        else:
            l.insert(0,str(a[i]))
    if n%2!=0:
        if i%2!=0:
            l.append(str(a[i]))
        else:
            l.insert(0,str(a[i]))
print(' '.join(l))

### FIXED CODE ###

n=int(input())
a=list(input().split())
b1=[]
b2=[]
if n%2==0:
    for i in range(n):
        if i%2!=0:
            b1.append(a[n-i])
        else:
            b2.append(a[i])
else:
    for i in range(n):
        if i%2==0:
            b1.append(a[n-1-i])
        else:
            b2.append(a[i])
 
b1.extend(b2)
 
print(" ".join(b1))
### BUGGY CODE ###

N, K = list(map(int, list(input().split())))
h = list(map(int, list(input().split())))
h = [0] + h

dp = [0x3f3f3f3f for _ in range(N+1)]
dp[1] = 0
for i in range(1, N+1):
    for j in range(1, K+1):
        if j > i:
            break
        dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))
print(dp[N])

### FIXED CODE ###

N, K = list(map(int, list(input().split())))
h = list(map(int, list(input().split())))
h = [0] + h

dp = [0x3f3f3f3f for _ in range(N+1)]
dp[1] = 0
for i in range(1, N+1):
    for j in range(1, K+1):
        if j > i:
            break
        dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))
print(dp[N])
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 1
for i in range(1,n):
    if p[i] == min(p[:i+1]):
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 0
t = p[0]
for i in range(n):
    if p[i] <= t:
        count += 1
        t = p[i]
print(count)
### BUGGY CODE ###

import math
S = input()
Q = int(input())

def reverse_list(S):
    S = list(S)
    S.reverse()
    return ''.join(S)

def moji_tuika(S, f, c):
    if f == 1:
        return c + S
    else:
        return S + c

q = []
for i in range(Q):
    temp = input().split()
    if len(temp) == 1:
        q.append(1)
    else:
        t = int(temp[0])
        f = int(temp[1])
        c = temp[2]
        q.append((t,f,c))

for i in q:
    if type(i) == int:
        S = reverse_list(S)
    elif i[0] == 2:
        S = moji_tuika(S,i[1],i[2])

print(S)


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

lr = 'left'

def reverse_list(lr):
    if lr == 'right':
        return 'left'
    else:
        return 'right'

def moji_tuika(S, f, c, lr):
    if f == 1 and lr == 'left':
        S.appendleft(c)
    elif f == 1 and lr == 'right':
        S.append(c)
    elif f == 2 and lr == 'left':
        S.append(c)
    else:
        S.appendleft(c)
    return S

q = []
for i in range(Q):
    temp = input().split()
    if len(temp) == 1:
        q.append(1)
    else:
        q.append(temp)

S = deque(list(S))
for i in q:

    if type(i) == int:
        lr = reverse_list(lr)
    elif int(i[0]) == 2:
        S = moji_tuika(S,int(i[1]),i[2],lr)
if lr == 'right':
    S.reverse()

S = ''.join(S)
print(S)
### BUGGY CODE ###

N = int(input())
S = str(input())
All = [i for i in range(1,N+1)]
R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
    elif S[i] == 'G':
        G.append(i+1)
    else:
        B.append(i+1)
ans = 0
count = 0
for k in R:
    for j in G:
        for i in B:
            fr = 0
            if k < j:
                fr += 1
            if j < i:
                fr += 1
            if k - j - 1 == j - i - 1:
                fr += 1

            if fr == 0:
                ans += 1

for k in R:
    for j in B:
        for i in G:
            fr = 0
            if k < j:
                fr += 1
            if j < i:
                fr += 1
            if k - j == j - i:
                fr += 1

            if fr == 0:
                ans += 1

for k in G:
    for j in R:
        for i in B:
            fr = 0
            if k < j:
                fr += 1
            if j < i:
                fr += 1
            if k - j - 1 == j - i - 1:
                fr += 1

            if fr == 0:
                ans += 1

for k in G:
    for j in B:
        for i in R:
            fr = 0
            if k < j:
                fr += 1
            if j < i:
                fr += 1
            if k - j - 1 == j - i - 1:
                fr += 1

            if fr == 0:
                ans += 1

for k in B:
    for j in R:
        for i in G:
            fr = 0
            if k < j:
                fr += 1
            if j < i:
                fr += 1
            if k - j - 1 == j - i - 1:
                fr += 1

            if fr == 0:
                ans += 1

for k in B:
    for j in G:
        for i in R:
            fr = 0
            if k < j:
                fr += 1
            if j < i:
                fr += 1
            if k - j - 1 == j - i - 1:
                fr += 1

            if fr == 0:
                ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
N -= 1
S = str(input())
count = S.count('R') * S.count('G') * S.count('B')
for i in range(N):
    for j in range(i,N+1):
        k = 2*j - i
        if k > N:
            pass
        elif S[i] == S[j] or S[i] == S[k] or S[j] == S[k]:
            pass
        else:
            count -= 1
print(count)
### BUGGY CODE ###

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

maxe = 0


for i in range(n-k+1):
   e = 0
   for j in range(i, i+k):
      e += sum([k for k in range(1, p[j]+1)])/p[j]

   maxe = max(maxe, e)

print(maxe)


### FIXED CODE ###

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

m = [(e + 1)/ 2 for e in p]

t = sum(m[0:k])
result = t
for i in range(n-k):
   t -= m[i]
   t += m[i+k]
   if t > result:
      result = t

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

# coding: utf-8
# Your code here!
import sys
import math
from collections import Counter

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)

N = int(sys.stdin.readline().strip())
arr = [sys.stdin.readline().strip() for i in range(N)]
mar_arr = [j for j in arr if j[0] == "M" or j[0] == "A" or j[0] == "R" or j[0] == "C" or j[0] == "H"]
ini_arr = [k[0] for k in mar_arr]
dic = Counter(ini_arr)
key_num = len(dic)
val_num = sum(v for v in dic.values())
if key_num < 3:
    print(0)
else:
    total = C(len(ini_arr), 3)
    for i in dic.values():
        if i == 2:
            total -= C(val_num - i, 1)
        elif i >= 3:
            total -= C(i, 2) * C(val_num - i, 1)  + C(i, 3)
    print(total)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

n = int(input())
t = [0] * n
for i in range(n):
    t[i] =input()[0]
t2 = [t.count(i) for i in ["M","A","R","C","H"]]
ans = 0
for i in range(5):
    for j in range(5):
        if j == i:
            break
        for k in range(5):
            if k == j:
                break
            ans += t2[i] * t2[j] * t2[k]
print(ans)
### BUGGY CODE ###

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

s_a = [0]
s_b = [0]
for i in range(n):
    s_a.append(s_a[i] + a[i])
for i in range(m):
    s_b.append(s_b[i] + b[i])
    
ans = 0
ok = m
for i in range(n+1):
    for j in range(ok+1):
        if s_a[i] + s_b[j] <= k:
            ans = max(ans, i+j)
            tmp = j
    ok = tmp

print(ans)

### FIXED CODE ###

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

s_a = [0]
s_b = [0]
for i in range(n):
    s_a.append(s_a[i] + a[i])
for i in range(m):
    s_b.append(s_b[i] + b[i])

ans = 0
tmp = m
for i in range(n+1):
    for j in range(tmp+1)[::-1]:
        if s_a[i] + s_b[j] <= k:
            ans = max(ans, i+j)
            tmp = j
            break
print(ans)
### BUGGY CODE ###

s=input()
k=int(input())
l=[i for i in s]
ans=[i for i in s]
mae=[]
for i in range(len(s)-1):
  for j in range(len(l)-1):
    nlen=len(l[j])
    lj=l[j+1]
    now=l[j]+lj[nlen-1:]
    ans.append(now)
    mae.append(now)
  l=mae
  mae=[]

ans=list(set(ans))
ans.sort()
print(ans[k-1])


### FIXED CODE ###

s=input()
k=int(input())
ans=[]

for i in range(len(s)):
  for j in range(i+1,min(k+i+1,len(s)+1)):
    ans.append(s[i:j])

ans=list(set(ans))
ans.sort()
print(ans[k-1])
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


N,M = inpl()
lines1 = defaultdict(set)

for _ in range(M):
    u,v = inpl()
    u -= 1
    v -= 1
    lines1[u].add(v)

S,T = inpl()
S -= 1
T -= 1

MEMO = [set() for _ in range(N)]
visited = [[False]*2 for _ in range(N)]

lines2 = defaultdict(set)
def dfs(start,s,n): #s: 今いる , n: 何歩目
    if n == 2:
        lines2[start] = copy.deepcopy(lines1[s])
    elif n == 1:
        if visited[s][1]:
            lines2[start].add(MEMO[s])
        else:
            for t in lines1[s]:
                MEMO[s].add(t)
                dfs(start,t,n+1)
    elif n == 0:
        for t in lines1[s]:
            dfs(start,t,n+1)


for i in range(N):
    dfs(i,i,0)


def search (s,w_0): #s->t
    global weight
    global q

    for t in list(lines2[s]):
        w = w_0 + 1
        if weight[t] > w:
            heapq.heappush(q, [w,t])
            weight[t] = w

weight = [INF]*N
weight[S] = 0
q = [[0,S]]
heapq.heapify(q)
while q:
    w,n = heapq.heappop(q)
    search(n,w)

if weight[T] == INF:
    print(-1)
else:
    print(weight[T])


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
    u,v = inpl()
    u -= 1
    v -= 1
    lines[u].add(v+N)
    lines[u+N].add(v+2*N)
    lines[u+2*N].add(v)

S,T = inpl()
S -= 1
T -= 1

def search (s,w_0): #s->t
	global weight
	global q

	for t in list(lines[s]):
		w = w_0 + 1
		if weight[t] > w:
			heapq.heappush(q, [w,t])
			weight[t] = w

# Start, S
weight = [INF]*(N*3)
weight[S] = 0
q = [[0,S]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)

ans = weight[T]

if ans == INF:
    print(-1)
else:
    print(ans//3)