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

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

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = -float("inf")
    max_L = -float("inf")
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    if max_L < 0: max_L = 0
    if max_R < 0: max_R = 0
    
    return max_L, max_R

#-----
cnt_brackets = []

for S in S_list:
    cnt_brackets.append( count_brackets(S) )


tmp_cnt1 = []
tmp_cnt2 = []

for cnt_L,cnt_R in cnt_brackets:
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )

tmp_cnt1.sort(key=lambda x: x[1])
tmp_cnt2.sort(key=lambda x: -x[0])


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

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

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = -float("inf")
    max_L = -float("inf")
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    if max_L < 0: max_L = 0
    if max_R < 0: max_R = 0
    
    return max_L, max_R


tmp_cnt1 = []  #  the number of "("  >=  the number of ")"
tmp_cnt2 = []  #  the number of "("  <   the number of ")"

for S in S_list:
    cnt_L,cnt_R = count_brackets(S)

    if cnt_L == cnt_R == 0:
        continue
    
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )


tmp_cnt1.sort(key=lambda x: x[1])
tmp_cnt2.sort(key=lambda x: -x[0])


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf")]*(N)
dp[0] = 0

for i in range(1,N):
    dp[i] = min([abs(h[i]-h[j])+dp[j] for j in range(max(i-K,0),i)])

print(dp[N-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*(N)

for i in range(1,N):
    now = h[i]
    dp[i] = min([abs(now-h[j])+dp[j] for j in range(max(i-K,0),i)])

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

import math
import collections

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0

    L = []
    R = []
    for i, a in enumerate(A):
        L.append(A[i] + (i+1))
        R.append((i+1)-A[i])

    l_min = min(min(L), min(R))
    l_max = max(max(L), max(R))

    for x in range(l_min, l_max + 1):
        ans += (L.count(x) * R.count(x))

    print(ans)
    return 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
#i_list = [a + i + 1 for i, a in enumerate(A)]

ans = 0
mp = {}
for i in range(N):
    i_kou = i + 1 + A[i]
    if i_kou in mp:
        mp[i_kou] += 1
    else:
        mp[i_kou] = 1
    j_kou = i + 1 - A[i]
    if j_kou in mp:
        ans += mp[j_kou]
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort(reverse=True)
F.sort()
ok = 10**12
ng = -1
while ng+1 < ok:
    c = (ok+ng) // 2
    k = K
    for a, f in zip(A, F):
        k -= max(0, a - c//f)
    if k >= 0:
        ok = c
    else:
        ng = c
print(ok)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort(reverse=True)
F.sort()
ok = 10**12
ng = -1
while ng+1 < ok:
    c = (ok+ng) // 2
    k = K
    for a, f in zip(A, F):
        k -= max(0, a - c//f)
    if k >= 0:
        ok = c
    else:
        ng = c
print(ok)
### BUGGY CODE ###

import numpy as np
N,M = map(int,input().split(" "))
ID = np.array([0]*N)

for _ in range(M):
    l = np.array([0]*N)
    L,R = map(int,input().split(" "))
    l[L-1:R] = 1
    ID+=l

print(len(ID[ID==M]))
    

### FIXED CODE ###

N,M = map(int,input().split(" "))
Min = 1
Max = N

for _ in range(M):
    L,R = map(int,input().split(" "))
    if L>Min:
        Min=L
    if R<Max:
        Max=R
if Max-Min>=0:
    print(Max-Min+1)
else:
    print(0)
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csc_matrix


def warshallFroyd(n):
    graph=[[0]*n for _ in range(n)]

    for i in range(n-1):
        graph[i][i+1]=1
        graph[i+1][i]=1

    graph[x-1][y-1]=1
    graph[y-1][x-1]=1

    graph=csc_matrix(graph)

    return floyd_warshall(graph)


n,x,y=map(int,input().split())
G=warshallFroyd(n)
D=[0]*n
for i in range(n):
    for j in range(i,n):
        D[int(G[i][j])] +=1

for i in D[1:]:
    print(i)

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)


def BFS(s):
    color=["white" for _ in range(n)]
    D=[float("inf") for _ in range(n)]

    color[s-1]="gray"
    D[s-1]=0
    queue=deque([s-1])

    while len(queue)!=0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return D


n,x,y=map(int,input().split())

M=[[] for _ in range(n)]
for i in range(n-1):
    M[i].append(i+1)
    M[i+1].append(i)
M[x-1].append(y-1)
M[y-1].append(x-1)

C=[0]*n
for i in range(n):
    for j in BFS(i+1)[i:]:
        C[j] +=1

for i in C[1:]:
    print(i)
### BUGGY CODE ###

def solve(N, A, S):
    dp = [set() for _ in range(N+1)]
    dp[N].add(0)
    for i in reversed(range(N)):
        if S[i] == "0":
            for v in dp[i+1]:
                dp[i].add(v)
                dp[i].add(v ^ A[i])
        else:
            if A[i] in dp[i+1]:
                for v in dp[i+1]:
                    dp[i].add(v)
            else:
                return 1
    return 0

def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        if S[-1] == "1":
            ans[i] = 1
        else:
            ans[i] = solve(N, A, S)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def solve(N, A, S):
    dp = []
    for i in reversed(range(N)):
        x = A[i]
        for v in dp:
            x = min(x, v^x)
        if x > 0:
            if S[i] == "0":
                dp.append(x)
            else:
                return 1
    return 0

def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        ans[i] = solve(N, A, S)
    for v in ans:
        print(v)

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

N = int(input())
S = []

for _ in range(N):
  S.append(input())

S_dict = sorted(list(set(S)))
#print(S_dict)
cnt = [0] * len(S_dict)

for i, item in enumerate(S_dict):
  cnt[i] = S.count(item)
#print(cnt)

m_cnt = max(cnt)

for i, item in enumerate(cnt):
  if m_cnt == item:
    print(S_dict[i])


### FIXED CODE ###

import collections

# input
N = int(input())
S = []

for _ in range(N):
  S.append(input())

cnt = collections.Counter(S)
cnt_sorted = sorted(cnt.items(), key=lambda x:x[1], reverse=True)
#print(cnt_sorted)

max = 0
pre = 0
ans = []
for v in cnt_sorted:
  max = v[1]
  if max >= pre:
    ans.append(v[0])
    pre = max
  else:
    break

ans.sort()
for a in ans:
  print(a)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

for i 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()
li = [0]
for i in range(1, n):
  incr = 1 if s[i-1] + s[i] == 'AC' else 0
  li.append(li[i-1] + incr)

for i in range(q):
  l, r = map(int, input().split())
  print(li[r-1] - li[l-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):

    BM = [[] for _ in range(20)]
    for j, a in enumerate(A):
        n = a
        for i in range(20, -1, -1):
            f = 2**i
            if n >= f:
                n -= f
                BM[i].append(j)

    error_print('-----')

    ans = N
    for i in range(0, N):
        min_r = sys.maxsize
        for bm in BM:
            ri = bisect.bisect_left(bm, i)
            if len(bm) == 0 or len(bm) == ri or len(bm) == ri + 1:
                r = N - 1
            else:
                r = bm[ri + 1] - 1
            min_r = min_r if min_r < r else r
        ans += min_r - i
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import time
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ans = 0
    S = 0
    X = 0
    r = 0
    for l in range(N):
        while r != N and S + A[r] == X ^ A[r]:
            S += A[r]
            X ^= A[r]
            r += 1
        ans += r - l
        S -= A[l]
        X ^= A[l]

    return ans


def main():
    N = read_int()
    A = read_int_n()

    print(slv(N, A))


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

import sys
input = sys.stdin.readline

n = int(input())
s = list(str(input()))
q = int(input())

#def segfunc(x,y):
    #return x | y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]={init_val[i]}
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1] | seg[2*i+2]

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = seg[k*2+1] | seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = res | seg[p]
    else:
        res = (res | seg[p]) | seg[q]
    return res

#####単位元######
ide_ele = set()

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, sys.stdin.readline().split())
    if t == '2':
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))
    else:
        i = int(x)-1
        c = {y}
        update(i, c)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = list(str(input()))
q = int(input())

s = [ord(c)-ord('a') for c in s]

#def segfunc(x,y):
    #return x | y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]={init_val[i]}
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1] | seg[2*i+2]

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = seg[k*2+1] | seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = res | seg[p]
    else:
        res = (res | seg[p]) | seg[q]
    return res

#####単位元######
ide_ele = set()

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, sys.stdin.readline().split())
    if t == '2':
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))
    else:
        i = int(x)-1
        c = {ord(y)-ord('a')}
        update(i, c)
### BUGGY CODE ###

iro = []
res = []
r = 0

N = int(input())
for i in range(N-1):
  a,b = input().split(" ")
  a = int(a)
  b = int(b)
  cr = 0
  for p in iro:
    if a not in p and b not in p:
      iro[cr].append(a)
      iro[cr].append(b)
      res.append(cr+1)
      break
    cr += 1
  else:
    r = cr
    iro.append([a,b])
    res.append(cr+1)
print(r+1)
for i in res:
  print(i)


### FIXED CODE ###

import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())

graph = [[] for _ in range(N + 1)]
 
for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
 
color = [0] * (N + 1)
queue = deque([1])
 
while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if number == color[V]:
            number += 1
        color[v] = number
        queue.append(v)
        number += 1
 
print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])
### BUGGY CODE ###

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

dp = [-1]*N
dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2,N):
  index = i - K
  if index < 0: index = 0
  cost_min = 10**9
  for j in range(index,i):
    ans = dp[j] + abs(h[i] - h[j])
    if cost_min > ans: cost_min = ans
  dp[i] = cost_min
print(dp[N-1])

### FIXED CODE ###

def main():
  N,K= map(int,input().split())
  h = list(map(int,input().split()))
  dp = [0]*N
  for i in range(1,N):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(i-K,0),i))
  print(dp[N-1])

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

def main():
    import sys
    readline = sys.stdin.buffer.readline

    from collections import deque

    h, w = map(int, readline().split())
    c = list(map(int, readline().split()))
    d = list(map(int, readline().split()))
    s = [readline().rstrip().decode('utf-8') for _ in range(h)]

    c = [i-1 for i in c]
    d = [i-1 for i in d]

    t0 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    t1 = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            t1.append((i, j))
    for i in t0:
        t1.remove(i)
    t1.remove((0, 0))

    check = [[-1]*w for _ in range(h)]
    q = deque()
    q.appendleft((c[0], c[1], 0))

    while q:
        y, x, b = q.pop()
        if x == d[1] and y == d[0]:
            print(b)
            exit()
        if check[y][x] == -1:
            check[y][x] = b
            for dy, dx in t0:
                ydy, xdx = y+dy, x+dx
                if (0 <= xdx < w) and (0 <= ydy < h):
                    if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                        q.append((ydy, xdx, b))
            for dy, dx in t1:
                ydy, xdx = y+dy, x+dx
                if (0 <= xdx < w) and (0 <= ydy < h):
                    if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                        q.appendleft((ydy, xdx, b+1))
    print(-1)

main()

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

c = [i-1 for i in c]
d = [i-1 for i in d]

t0 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t1 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        t1.append((i, j))
for i in t0:
    t1.remove(i)
t1.remove((0, 0))

check = [[-1]*w for _ in range(h)]
q = deque()
q.appendleft((c[0], c[1], 0))

while q:
    y, x, b = q.pop()
    if x == d[1] and y == d[0]:
        print(b)
        exit()
    if check[y][x] == -1:
        check[y][x] = b
        for dy, dx in t0:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.append((ydy, xdx, b))
        for dy, dx in t1:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.appendleft((ydy, xdx, b+1))
print(-1)
### BUGGY CODE ###

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

maxA = max(A)
K = len(str(bin(maxA)))-2
ans = 0
for k in range(K):
    N1 = 0
    N1 = sum(( (a >> k) & 1) for a in A )
    N0 = N-N1
    ans += (((1<<k)%M) *N0 *N1) % M

ans %= M    
print(int(ans))


### FIXED CODE ###

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

ans = 0
for k in range(61):
    N1 = 0
    N1 = sum([1 for a in A if ( (a >> k) & 1)])
    ans += (((1<<k)) *(N-N1) *N1)
    ans %= M    

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

import numpy as np
import sys
N = int(raw_input())
nums = map(int, raw_input().split())
for i in range(N):
    nums_tmp = nums[0:i] + nums[i+1:N]
    nums_tmp = np.array(nums_tmp)
    print(int(np.median(nums_tmp)))
sys.exit()
num_t = []
index_t = []
for i,num in enumerate(nums):
    num_t.append([num, i])
num_t = sorted(num_t, key=lambda x: x[0])
for a in num_t:
    index_t.append(a[1])
for i in range(N):
    num_tmp = num_t
    idx = index_t.index(i)
    num_tmp = num_tmp[0:idx] + num_tmp[idx+1:N]
    print(num_tmp[(N/2) - 1][0])

### FIXED CODE ###

N = int(raw_input())
nums = map(int, raw_input().split())
num_tmp = []
for a in nums:
    num_tmp.append(a)
nums.sort()
med_1 = nums[N/2 - 1]
med_2 = nums[N/2]
for i in range(N):
    if num_tmp[i] <= med_1:
        print(med_2)
    elif num_tmp[i] >= med_2:
        print(med_1)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
#print(N, K, Q)

A = []
point = [K]*N
#print(point)

for i in range(Q):
  A.append(int(input()))
  i += 1
#print(A)

for i in A:
  for j in range(N):
    if point[j] > 0 and j != (i - 1):
      point[j] -= 1
    else:
      continue

for i in point:
  if i > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
point = [0] * N

for i in range(Q):
    point[int(input()) - 1] += 1
    i += 1

sum_point = sum(point)

for i in range(N):
    ans = K - (sum_point - point[i])
    if ans > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
import itertools

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N, K = MI()
    p = LI()
    c = itertools.combinations(p, K)
    clist = list(c)
    cn = len(clist)

    for i in range(cn):
        sumi = int(sum(clist[i]))
        if i == 0:
            min =sumi
        if min > sumi:
            min = sumi

    print(min)
    #print(len(clist))
    #print(sum(clist[2]))



if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
import itertools

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N, K = MI()
    p = LI()
    ps = sorted(p)
    ans = 0

    for i in range(K):
        ans += ps[i]

    print(ans)
    #print(len(clist))
    #print(sum(clist[2]))



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

import sys
input = sys.stdin.readline

from heapq import heappush, heappop

INF = float('inf')

# 単一始点最短経路を求める（Dijkstra法）
def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2, wt in adjList[vNow]:
            c2 = cNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))
    return costs


N, M = map(int, input().split())
edges = []
v0s = [[] for _ in range(N)]
v2s = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    edges.append((u, v))
    v0s[v].append(u)
    v2s[u].append(v)

S, T = map(int, input().split())
S, T = S-1, T-1

adjL = [[] for _ in range(N)]
for u, v in edges:
    for v0 in v0s[u]:
        for v2 in v2s[v]:
            adjL[v0].append((v2, 1))

costs = Dijkstra(adjL, S)

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


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

INF = float('inf')

def bfsMinCosts(adjList, vSt):
    numV = len(adjList)
    costs = [INF] * numV
    costs[vSt] = 0
    Q = deque([vSt])
    while Q:
        vNow = Q.popleft()
        cNow = costs[vNow]
        for v2 in adjList[vNow]:
            if costs[v2] == INF:
                costs[v2] = cNow + 1
                Q.append(v2)
    return costs

N, M = map(int, input().split())
adjL = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    adjL[3*u+0].append(3*v+1)
    adjL[3*u+1].append(3*v+2)
    adjL[3*u+2].append(3*v+0)

S, T = map(int, input().split())
S, T = S-1, T-1

costs = bfsMinCosts(adjL, 3*S+0)

if costs[3*T+0] == INF:
    print(-1)
else:
    print(costs[3*T+0]//3)