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

from functools import lru_cache
N,W=map(int,input().split())
weights0,profits0 = [0]*N, [0]*N
for i in range(N):
    weights0[i],profits0[i] = map(int,input().split())
weights0 = tuple(weights0)
profits0 = tuple(profits0)
 
@lru_cache(maxsize=100)
def knapsack_recursive(weights, profits, capacity, currentIndex):
    if capacity <= 0 or currentIndex >= len(profits): return 0
    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(weights, profits, capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(weights, profits, capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():
    res = knapsack_recursive(weights0, profits0, W, 0)
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

import sys

n = int(input())
alphabet = [chr(ord("a") + i) for i in range(26)]
count = [[0] * 26 for _ in range(n)]
for i in range(n):
    for s in sys.stdin.readline().strip():
        count[i][alphabet.index(s)] += 1

uniq = set(list(map(tuple, count)))
ans = 0
for u in uniq:
    n = count.count(list(u))
    ans += n * (n - 1) // 2
print(ans)


### FIXED CODE ###

import sys
import collections

n = int(input())
lst = [None] * n
for i in range(n):
    lst[i] = "".join(sorted(list(sys.stdin.readline().strip())))

ans = 0
for v in collections.Counter(lst).values():
    ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]

g = [[] for _ in range(n)]

for u, v, w in uvw:
    u -= 1
    v -= 1
    g[u].append([v, w])
    g[v].append([u, w])


WHITE = 0
GRAY = 1
BLACK = 2

ds = [0] * n
colors = [WHITE] * n
ps = [-1] * n


def dfs(s):
    global ds, colors, ps

    stack = []

    ds[s] = 0
    colors[s] = BLACK
    ps[s] = -1
    stack.append(ds[s])

    while stack:
        u = stack[-1]
        colors[u] = GRAY

        for v, w in g[u]:
            if colors[v] == WHITE:
                stack.append(v)
                ds[v] = ds[u] + w
                ps[v] = u
                break

        else:
            stack.pop()
            colors[u] = BLACK

    return ds, ps


dfs(0)

for d in ds:
    print(d % 2)


### FIXED CODE ###

n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]

g = [[] for _ in range(n)]

for u, v, w in uvw:
    u -= 1
    v -= 1
    g[u].append([v, w])
    g[v].append([u, w])


WHITE = 0
GRAY = 1
BLACK = 2

ds = [0] * n
colors = [WHITE] * n
ps = [-1] * n


def dfs(s):
    global ds, colors, ps

    stack = []

    ds[s] = 0
    colors[s] = BLACK
    ps[s] = -1
    stack.append(ds[s])

    while stack:
        u = stack[-1]
        colors[u] = GRAY

        for v, w in g[u]:
            if colors[v] == WHITE:
                stack.append(v)
                ds[v] = ds[u] + w
                ps[v] = u
                g[u].remove([v, w])
                g[v].remove([u, w])
                break

        else:
            stack.pop()
            colors[u] = BLACK

    return ds, ps


dfs(0)

for d in ds:
    print(d % 2)
### BUGGY CODE ###

import collections
from itertools import accumulate, combinations

n = int(input())
a = list(map(int,input().split()))
ac = [0] + list(accumulate(a))
c = collections.Counter(ac)

cnt = 0
for v in c.values():
    if v >= 2:
        cnt += len(list(combinations(list(range(v)),2)))
print(cnt)

### FIXED CODE ###

import math
from collections import Counter
from itertools import accumulate

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(input())
a = list(map(int,input().split()))
ac = [0] + list(accumulate(a))
c = Counter(ac)

cnt = 0
for v in c.values():
    if v >= 2:
        cnt += C(v,2)
print(cnt)
### BUGGY CODE ###

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

place = 1
way = [1]
for i in range(n):
    if a[place-1] in way:
        break
    else:
        place = a[place-1]
        way.append(place)
ex = way.index(a[place-1])
loop = way[ex:]
if k <= ex:
    print(way[k])
else:
    k -= ex
    print(loop[k%len(loop)])


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
alr = [0 for i in range(n)]
now = 1
path = [now]

for i in range(k):
    now = a[now-1]
    # if now in path:
    #     now = path[path.index(now) + (k-i-1)%(len(path) - path.index(now))]
    #     break
    if alr[now-1] != 0:
        now = path[path.index(now) + (k-i-1)%(len(path) - path.index(now))]
        break
    path.append(now)
    alr[now-1] += 1

print(now)
### BUGGY CODE ###

k = int(input())
s = input()
n = len(s)
mod = 10 ** 9 + 7

fac = [1] * (n + k + 2)
for i in range(1, n + k + 1):
    fac[i] = fac[i - 1] * i % mod


def c(n, k):
    return fac[n] * pow(fac[n - k] * fac[k] % mod, mod - 2, mod) % mod


ans = 0
for i in range(k + 1):
    ans += c(n - 1 + k - i, k - i) * \
        pow(25, k - i, mod) * pow(26, i, mod) % mod
    ans %= mod
print(ans)


### FIXED CODE ###

k = int(input())
s = input()
n = len(s)
mod = 10 ** 9 + 7

fac = [1] * (n + k + 2)
for i in range(1, n + k + 1):
    fac[i] = fac[i - 1] * i % mod


def c(n, k):
    return fac[n] * pow(fac[n - k] * fac[k] % mod, mod - 2, mod) % mod


ans = 0
for i in range(k + 1):
    ans += c(n - 1 + k - i, k - i) * \
        pow(25, k - i, mod) * pow(26, i, mod) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
c = 0
for i in range(0,n):
  tmp = 0
  for j in range(0,i):
    if(p[i] <= p[j]):
      tmp = tmp + 1
  if(tmp == len(p[:i])):
    c += 1
      
print(c)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
c = 1
tmp = p[0]
for i in range(1,n):
  tmp = min(tmp,p[i])
  if(tmp >= p[i]):
    c = c + 1
      
print(c)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

memo = []
for a in A:
  if(a not in memo):
    memo.append(a)
  else:
    memo.remove(a)
print(len(memo))


### FIXED CODE ###

N = int(input())
A = [input() for _ in range(N)]

memo = {}
for a in A:
  if(a not in memo):
    memo[a] = 0
  else:
    memo.pop(a)
print(len(memo))
### BUGGY CODE ###

n = int(input())
c = [[int(i) for i in input().split()] for i in range(n)]
max_length = 0
for i in range(n-1):
    for j in range(i+1,n):
        length = abs(c[i][0] - c[j][0]) + abs(c[i][1] - c[j][1])
        max_length = max(max_length, length)
print(max_length)

### FIXED CODE ###

n = int(input())
c = [[int(i) for i in input().split()] for i in range(n)]
z = []
w = []
for i in range(n):
    z.append(c[i][0] + c[i][1])
    w.append(c[i][1] - c[i][0])
ans = max(max(z)-min(z), max(w)-min(w))
print(ans)
### BUGGY CODE ###

import queue


N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
visited = [False] * N
q = queue.Queue()

def bfs():
    max_cnt = 0
    while not q.empty():
        u = q.get()
        cnt = 1
        for v in edges[u]:
            if colors[u][v] != -1:
                continue

            while cnt in colors[u]:
                cnt += 1

            colors[u][v] = cnt
            colors[v][u] = cnt
            q.put(v)
            max_cnt = max(max_cnt, cnt)
    return max_cnt


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

q.put(0)
max_cnt = bfs()
print(max_cnt)
for a, b in AB:
    print(colors[a][b])


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

n = int(input())
A = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    A[a].append([b, i])

ans = [0] * (n - 1)


def col(now, color):
    c = 1
    for (b, j) in A[now]:
        if c == color:
            c += 1
        ans[j] = c
        col(b, c)
        c += 1


col(0, 0)
print(max(ans))
for a in ans:
    print(a)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
prv_total =0
cnt = 0
for i in range(n-1):
  total = prv_total + a[i]
  nxt_total = total+a[i+1]
  while total*nxt_total >= 0:
    if total == nxt_total:
      if total > 0:
        a[i+1] -= 1
        nxt_total -=1
      else:
        a[i+1] += 1
        nxt_total +=1        
    elif total-nxt_total == 1:
      a[i+1] -= 1
      nxt_total -=1
    elif nxt_total-total == 1:
      a[i+1] += 1
      nxt_total += 1
    elif (total<nxt_total and total >= 0) or (nxt_total<total and nxt_total >= 0):
      total -= 1
      nxt_total -= 1
    elif (total<nxt_total and nxt_total <= 0) or (nxt_total<total and total <= 0):
      total += 1
      nxt_total += 1
    cnt += 1
  prv_total = total

total = prv_total + a[-1]
if total == 0:
  cnt += 1
  
print(cnt)

### FIXED CODE ###

from itertools import accumulate
import copy

def sol(acmA, sign=1):    
  add = 0
  ans = 0
  if sign==1:
    if acmA[0] <= 0:
      add = -acmA[0]+1
      ans = abs(-acmA[0]+1)
      acmA[0] = 1
  else:  
    if acmA[0] >= 0:
      add = -acmA[0]-1
      ans = abs(-acmA[0]-1)
      acmA[0] = -1      
      
  for i in range(1,N):
    acmA[i] += add
    tmp_add = 0
    if sign == 1:
      if i%2==0:
        if acmA[i] <=0:
          tmp_add = -acmA[i]+1
      else:
        if acmA[i] >=0:
          tmp_add = -acmA[i]-1
    else:
      if i%2==1:
        if acmA[i] <=0:
          tmp_add = -acmA[i]+1
      else:
        if acmA[i] >=0:
          tmp_add = -acmA[i]-1     
   
    #print(i, tmp_add, acmA[i])
    acmA[i] += tmp_add
    add +=  tmp_add
    ans +=abs(tmp_add)
  if acmA[-1] == 0: return ans +1
  else: return ans

N = int(input())
A = list(map(int,input().split()))
acmA = list(accumulate(A))
acmA2 = copy.deepcopy(acmA)
print(min(sol(acmA, 1), sol(acmA2, -1)))
### BUGGY CODE ###

# coding: utf-8
A,B,N=map(int,input().split())

min_x = 1
max_x = N

def f(x):
    y = (A*x)//B - A*(x//B)
    return y

def tren_isOK(x1,x2):
    if f(x1) >= f(x2):
        return True
    else:
        return False


def treary_search():
    left = min_x
    right = max_x

    while abs(right - left) >10**(-8):
        p1 = (right + 2*left)/3
        p2 = (2*right + left)/3

        if tren_isOK(p1,p2):
            right = p2
        else:
            left = p1
    
    return right

x=treary_search()
ans=max(f(int(x)),f(int(x)+1))
print(ans)

### FIXED CODE ###

# coding: utf-8
A,B,N=map(int,input().split())

min_x = 1
max_x = N

def f(x):
    y = (A*x)//B - A*(x//B)
    return y
    
ans=f(min(B-1,N))
print(ans)
### BUGGY CODE ###

import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_left # bisect_left(list, value)
#from fractions import gcd
from operator import mul
from functools import reduce

sys.setrecursionlimit(10**7)
n, a, b = map(int, input().split())
div = 10**9+7

num = (2**n)%div

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, n+2):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

num -= cmb(n, a, mod)
num -= cmb(n, b, mod)
num %= div

print(num-1)



### FIXED CODE ###

import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_left # bisect_left(list, value)
#from fractions import gcd
enu = enumerate

sys.setrecursionlimit(10**7)
n, a, b = map(int, input().split())
mod = 10**9 + 7

def cmb(n, r, p):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = 1
    for i in range(n, n - r, -1):
        over = over * i % p
    under = 1
    for i in range(1, r + 1):
        under = under * i % p
    inv = pow(under, p - 2, p)
    return over * inv % p

cnt = pow(2, n, mod)
ng1 = cmb(n, a, mod)
ng2 = cmb(n, b, mod)

res = (cnt - ng1 - ng2 - 1) % mod

print(res)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))
asd=a[:]
asd.sort(key=lambda x:x[1])
asd.sort(key=lambda x:x[0])
keep,ki=0,1
for i in asd:
    if keep==i[0]:ki+=1
    else:keep,ki=i[0],1
    a[a.index(i)]=str(i[0]).zfill(6)+str(ki).zfill(6)
for i in a:
    print(i)

### FIXED CODE ###

n,m=map(int,input().split())
l=[]
for i in range(m):
    a=list(map(int,input().split()))
    a.append(i)
    l.append(a)
l.sort(key=lambda x:x[1])
l.sort(key=lambda x:x[0])
j,y=0,1
for i in range(m):
    x=l[i].pop(0)
    y=y+1 if j==x else 1
    j=x
    l[i][0]=str(x).zfill(6)+str(y).zfill(6)
l.sort(key=lambda x:x[1])
for i in l:print(i[0])
### BUGGY CODE ###

import numpy as np

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

light = np.array([[-1, -1] for _ in range(H*W)])

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        
        if light[W*i+j][0] == -1:
            tmp = 0
            tate = i
            while tate < H and S[tate][j] == '.':
                tmp += 1
                tate += 1
            for k in range(tmp):
                light[W*(i+k)+j][0] = tmp
        
        if light[W*i+j][1] == -1:
            tmp = 0
            yoko = j
            while yoko < W and S[i][yoko] == '.':
                tmp += 1
                yoko += 1
            for k in range(tmp):
                light[W*i+j+k][1] = tmp


print(np.max(light.sum(axis=1))-1)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
up = np.zeros((H, W), dtype=int)
down = np.zeros((H, W), dtype=int)
left = np.zeros((H, W), dtype=int)
right = np.zeros((H, W), dtype=int)
 
for i in range(H):
    up[i] = (up[i-1] + 1) * S[i]
    down[-i-1] = (down[-i] + 1) * S[-i-1]

for i in range(W):
    left[:, i] = (left[:, i-1] + 1) * S[:, i]
    right[:, -i-1] = (right[:, -i] + 1) * S[:, -i-1]

print(np.max(up+down+left+right)-3)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

A.sort()
sumv = 0
for i, vi in enumerate(A):
    for vj in A[i+1:]:
        sumv += vi^vj
    sumv %= mod
print(sumv)

### FIXED CODE ###

import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
A = np.array(input().split(), np.int)
#print(A)

cnt = 0
for i in range(61):
    B = (A>>i)&1
    z = np.count_nonzero(B)
    cnt += z*(N-z)*(2**(i))
    cnt %= MOD

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

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

for i in range(Q):
    Query = list(input().split())
    #print(Query)
    if len(Query) == 1:
        S = S[::-1]
        #print(S)
    else:
        if Query[1] == '1':
            S = Query[2] + S
            #print(S + '+++1')
        else:
            S += Query[2]
            #print(S + '+++2')

print(S)

### FIXED CODE ###

from collections import deque

S = input()
S = deque(S)
Q = int(input())
Query1 = 0
flag = False
for i in range(Q):
    Queryi = input().split()
    if Queryi[0] == '1':
        Query1 += 1
        flag = not flag
    else:
        if (Queryi[1] == '1') ^ flag:
            S.appendleft(Queryi[2])
        else:
            S.append(Queryi[2])

if Query1 % 2 != 0:
    S.reverse()

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

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

ans = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
for x in range(K+1):
    for y in range(K+1):
        if S - x - y <= K and S - x - y >= 0:
            ans += 1
print(ans)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
an = []
ans = []
for i in range(x):
    for j in range(y):
        an.append(lisa[i]+lisb[j])
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for i in range(z):
    for j in range(min(3000,x*y)):
        ans.append(lisc[i]+an[j])
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

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

for i in range(0, n):
    for j in range(i, n):
        sum += a[j]
        if sum == 0:
            count += 1
    sum = 0
print(count)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
b = 1
c = 0

for i in range(n):
    s.append(s[i] + a[i])
s.sort()
s.append('\0')

for i in range(1, len(s)):
    if s[i] == s[i-1]:
        b += 1
        continue
    c += int(b*(b-1)/2)
    b = 1
print(c)
### BUGGY CODE ###

from collections import defaultdict, deque

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1

maze = []
for _ in range(H):
    row = list(input())
    maze.append(row)

def dfs(i, j, cnt):
    mapped[i][j] = cnt

    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        x = i + dx
        y = j + dy
        if 0 <= x < H and 0 <= y < W and maze[x][y] == "." and mapped[x][y] == -1:
            dfs(x, y, cnt)
        elif 0 <= x < H and 0 <= y < W and maze[x][y] == "#" and (i, j) not in edges[cnt]:
            edges[cnt].add((i, j))

cnt = 0
mapped = [[-1] * W for _ in range(H)]
edges = defaultdict(set)
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." and mapped[i][j] == -1:
            dfs(i, j, cnt)
            cnt += 1

invalid_pos = set([(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)])
# edges からワープで移動できる島を繋いで、グラフを作る
g = defaultdict(set)
for num in edges:
    for i, j in edges[num]:
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if (dx, dy) in  invalid_pos: continue
                x = i + dx
                y = j + dy
                if 0 <= x < H and 0 <= y < W and mapped[x][y] != -1 and mapped[x][y] != num and mapped[x][y] not in g[num]:
                    g[num].add(mapped[x][y])
                    g[mapped[x][y]].add(num)

# gでのstart, endの最短距離をbfsで求める
start = mapped[ch][cw]
end = mapped[dh][dw]
q = deque([(start, 0),])
seen = set()

isFind = False
while q:
    size = len(q)
    for _ in range(size):
        node, d = q.popleft()
        seen.add(node)
        if node == end:
            print(d)
            isFind = True
            break
        for adj in g[node]:
            if adj not in seen:
                q.append((adj, d+1))
    if isFind:
        break

if not isFind:
    print(-1)



### FIXED CODE ###

from collections import defaultdict, deque

def main():
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    maze = [input() for _ in range(H)]

    INF = 10**12
    path = [[INF] * W for _ in range(H)] # 各マスへの移動コスト
    
    # walk:移動A, warp:移動B
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[ch][cw] = 0
    q.append((ch, cw, 0))

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk: #移動A
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s)) # なぜleft?

        for dx, dy in warp: #移動B
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s+1)) # なぜright?

    ans = path[dh][dw] if path[dh][dw] != INF else "-1"
    print(ans)

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

#
import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def next_kenp(node, edges):
    nodes = set()
    nodes2 = set()
    for n1 in edges[node]:
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)
    for n2 in nodes2:
        for n3 in edges[n2]:
            nodes.add(n3)
    return nodes


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[(u, 0)].append((v, 1))
        edges[(u, 1)].append((v, 2))
        edges[(u, 2)].append((v, 0))

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

    # print(new_edges)

    dones = set()
    que = [((s, 0), 0)]
    while que:
        node, step = que.pop(0)

        next_nodes = edges[node]
        # print(next_nodes)
        for n, l in next_nodes:
            if n == t and l == 0:
                print((step + 1) // 3)
                exit()

            if (n, l) not in dones:
                que.append(((n, l), step + 1))
                dones.add((n, l))
    print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[(u, 0)].append((v, 1))
        edges[(u, 1)].append((v, 2))
        edges[(u, 2)].append((v, 0))

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

    # print(new_edges)

    dones = set()
    que = deque()
    que.append(((s, 0), 0))
    while que:
        node, step = que.popleft()

        next_nodes = edges[node]
        # print(next_nodes)
        for n, l in next_nodes:
            if n == t and l == 0:
                print((step + 1) // 3)
                exit()

            if (n, l) not in dones:
                que.append(((n, l), step + 1))
                dones.add((n, l))
    print(-1)


if __name__ == '__main__':
    main()