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

import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [None]*N
E = []
for n in range(N):
	V[n] = list(map(int,inputs().split()))
	V[n][0] -= V[n][2]
	V[n][1] -= V[n][2]
	E.append([V[n][0],1,V[n][2]])
	E.append([V[n][1],-1,V[n][2]])
D = [int(inputs()) for p in [0]*Q]
E.sort(key = lambda x:x[0])
mini = 1000000001
kouho = [1000000001]
q = 0
d = D[0]
flag = False
for e in E:
	while(e[0] > d):
		for k in kouho:
			mini = min(k,mini)
		if mini < 1000000001:
			print(mini)
			mini = 1000000001
		else:
			print(-1)
			mini = 1000000001
		if q < Q-1:
			q = q + 1
			d = D[q]
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		kouho.append(e[2])
	elif e[1] == -1:
		kouho.remove(e[2])
for t in [None]*(Q-q):
	print(-1)

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
import sys
sys.setrecursionlimit(10**6)
def dfs(x):
    global ans
    check[x]=True
    count=0
    for i in graph[x]:
        if not check[i]:
            count+=1
            dfs(i)
    if x==0:
        temp=1
        for i in range(count):
            temp=temp*(k-1-i)%INF
        ans=ans*temp%INF
    else:
        temp=1
        for i in range(count):
            temp=temp*(k-2-i)%INF
        ans=ans*temp%INF
dfs(0)
print((ans*k)%INF)
        


### FIXED CODE ###

INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
import sys
sys.setrecursionlimit(10**6)
stack=[0]
ans=1
while len(stack)>0:
    x=stack.pop()
    check[x]=True
    count=0
    for i in graph[x]:
        if not check[i]:
            count+=1
            stack.append(i)
    if x==0:
        temp=1
        for i in range(count):
            temp=temp*(k-1-i)%INF
        ans=ans*temp%INF
    else:
        temp=1
        for i in range(count):
            temp=temp*(k-2-i)%INF
        ans=ans*temp%INF
print((ans*k)%INF)
### BUGGY CODE ###

def divs(n):
    res = []
    i = 1
    while i**2 <= n:
        if n%i == 0: 
            res.append(i)
            if i**2 != n:
                res.append(n//i)
        i+=1 
    return res


def main():
    n = int(input())
    al_0 = list(map(int, input().split()))
    if sum(al_0) == 0:
        print(0)
        return

    al = [0] + al_0
    divs_cnts = [0]*(n+1)
    ans = []
    for i in range(n,0,-1):
        if divs_cnts[i]%2 != al[i]%2:
            ans.append(i)
            div_l = divs(i)
            for d in div_l:
                divs_cnts[d] += 1

    print(len(ans))
    print(*ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def divs(n):
    res = []
    i = 1
    while i**2 <= n:
        if n%i == 0: 
            res.append(i)
            if i**2 != n:
                res.append(n//i)
        i+=1 
    return res


def main():
    n = int(input())
    al_0 = list(map(int, input().split()))
    if sum(al_0) == 0:
        print(0)
        return

    al = [0] + al_0
    divs_cnts = [0]*(n+1)
    ans = []
    for i in range(n,0,-1):
        if divs_cnts[i]%2 != al[i]%2:
            ans.append(i)
            div_l = divs(i)
            for d in div_l:
                divs_cnts[d] += 1

    print(len(ans))
    print(*ans)


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

n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
#print(l)
for i in l:
    a=1
    for j in l:
        if i[0]==j[0] and i[1]>j[1]:
            a+=1
    print(str('%06d'%i[0])+str('%06d'%a))        

### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s=[]
for i in enumerate(l):
    s.append(i)
s=sorted(s,key=lambda x:(x[1][0],x[1][1]))
#print(s)
a=1
for i in range(m):
    if i==0:
        s[0][1][1]=1
    elif s[i][1][0]==s[i-1][1][0]:
        a+=1
        s[i][1][1]=a
    elif s[i][1][0]!=s[i-1][1][0]:
        a=1
        s[i][1][1]=a
#print(s)
s=sorted(s,key=lambda x:x[0])
#print(s)
for i in s:
    print('%06d'%i[1][0]+'%06d'%i[1][1])
### BUGGY CODE ###

n,k,q = map(int,input().split())
points = [k for i in range(n)]
winner = [int(input()) for i in range(q)]
# print(points,winner)
for i in range(q):
    # print(i,'番目の問題')
    points = [j-1 for j in points]
    # print(winner[i])
    points[winner[i]-1] += 1
for i in points:
    if i <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n,k,q = map(int,input().split())
points = [k for i in range(n)]
winner = [int(input()) for i in range(q)]
points = [i-q for i in points]
for i in range(q):
    points[winner[i]-1] += 1
for i in points:
    if i <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u,s=0):
        route[u]=True
        score[u]=s
        res=-inf
        if u==0:res=0
        for v,c in ot[u]:
            if route[v]:
                if s+c>score[v]:
                    return inf
                continue
            ret=dfs(v,s+c)
            if ret==inf:return inf
            res=max(res,ret+c)
        route[u]=False
        return res

    inf = 10 ** 14
    n, m = MI()
    ot = defaultdict(list)
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ot[b].append([a, c])

    score = [-inf] * n
    score[0]=0
    route=[False]*n
    ans=dfs(n-1)
    if ans==inf:
        print("inf")
    else:
        print(ans)

main()


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 14
    n, m = MI()
    ee = []
    # スコアの正負を逆にし、最小値を求める問題に置き換える
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ee.append([a, b, -c])
    # ベルマン・フォードで最小スコアを計算
    # n-1回やっても更新があるということは負の閉路があるということ
    # 負の閉路がなければ答えを出力して終了
    score = [inf] * n
    score[0] = 0
    for _ in range(n):
        change = False
        for a, b, c in ee:
            if score[a] + c < score[b]:
                score[b] = score[a] + c
                change = True
        if not change:
            print(-score[n - 1])
            exit()
    # 負の閉路がある場合は、その影響がゴールまで届くかをチェック
    reachable = [False] * n
    for _ in range(n):
        for a, b, c in ee:
            if reachable[a]:reachable[b]=True
            if score[a] + c < score[b]:
                score[b] = score[a] + c
                reachable[b] = True
        if reachable[n - 1]:
            print("inf")
            exit()
    print(-score[n-1])

main()
### BUGGY CODE ###

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

if num[1] == 0:     
  count_ac_all = 0
  count_wa_all = 0 

else:  
  num_list = []
  for i in range(0,num[1]):
    num_list.append(list(input().split()))

  group=set()
  new_num = []

  for i in range(0,num[1]):
    group.add(num_list[i][0])

  set_list = list(group)

  for i in range(0,len(set_list)):
    for j in range(0,len(num_list)):
      if num_list[j][0] == set_list[i]:
        new_num.append(num_list[j])

  count_ac = 0
  count_wa = 0
  count_ac_all = 0
  count_wa_all = 0
  base = new_num[0][0]
  count = 0


  for i in range(0,len(new_num)):
    if not new_num[i][0] == base:
      base = new_num[i][0]
      count = 0
      count_ac = 0
      count_wa = 0

    if count == 0:
      if new_num[i][1] == 'WA':
        count_wa = count_wa+1
      elif new_num[i][1] == 'AC':
        count_ac = count_ac+1
        count = 1

    if count == 1:
      count_ac_all = count_ac_all + count_ac
      count_wa_all = count_wa_all + count_wa
      count = -1
    
print(count_ac_all,count_wa_all)

### FIXED CODE ###

import numpy as np

n,m = map(int,input().split())
base = np.zeros(n)
pena = np.zeros(n)

for i in range(m):
  s = list(input().split())
  if (s[1] == "WA") and (base[int(s[0])-1] == 0):
    pena[int(s[0])-1] += 1
  elif (s[1] == "AC"):
    base[int(s[0])-1] = 1
    
ans_1 = np.multiply(base,pena)
print(int(np.sum(base)),int(np.sum(ans_1)))
### BUGGY CODE ###

N = int(input())

d_list = [1]

a = 1
while True:
  if 6**a <= N:
    d_list.append(6**a)
    a += 1
  else:
    break
a = 1
while True:
  if 9**a <= N:
    d_list.append(9**a)
    a += 1
  else:
    break
d_list.sort(key=lambda x:-x)

rest = N
cnt = 0
while True:
  if rest < 6:
    cnt = rest
    print(cnt)
  else:
    for num in d_list:
      if rest >= num:
        cnt += 1
        rest -= num
        break


### FIXED CODE ###

N = int(input())
INF = 10**6
dp = [INF] * (max(9, N)+1)
dp[0] = 0
for i in range(N):
  n = m = 0
  while i+9**n <= N:
    dp[i+9**n] = min(dp[i+9**n], dp[i] + 1)
    n += 1
  while i+6**m <= N:
    dp[i+6**m] = min(dp[i+6**m], dp[i] + 1)
    m += 1
print(dp[N])
### BUGGY CODE ###

n,m = map(int,input().split())
dp = [0]+[10**8+10]*(2**n-1)
#len(dp)==16　（2**n）　扉の開閉状態
#dp: その開閉状態を実現するための鍵の値段の最小値

#それぞれの鍵について
for i in range(m):
  a,b = map(int,input().split())
  #x: 開く扉の番号
  #2**(1-1)==000000000001   2**(12-1)==100000000000
  #sは　100010111000みたいなやつ（その鍵で開く扉が１）
  s = sum([2**(x-1) for x in list(map(int,input().split()))])
  for j in range(2**n):
    #| : or
    #（ある状態＋その鍵を使って開けられるやつ）の状態　　もともとの数値か、鍵を使うか
    dp[j|s] = min(dp[j|s],dp[j]+a)
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)



### FIXED CODE ###

n,m = map(int,input().split())
dp = [0]+[10**8+10]*(2**n-1)
for i in range(m):
  a,b = map(int,input().split())
  s = sum([2**(x-1) for x in list(map(int,input().split()))])
  for j in range(2**n):
    dp[j|s] = min(dp[j|s],dp[j]+a)
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)
### BUGGY CODE ###

n = int(input())
mod = 10**9 + 7
a = list(map(int,input().split()))
il = [[]for i in range(n)]
for i in range(n+1):
    il[a[i]-1].append(i)
    if len(il[a[i]-1]) > 1:
        p,q = il[a[i]-1]
comb = 1
comb2 = 1
c = p + n - q
for i in range(n+1):
    comb = comb*(n+1-i)//(i+1)
    if c >= i:
        print((comb-comb2)%mod)
        comb2 = comb2*(c-i)//(i+1)
    else:
        print(comb%mod)

### FIXED CODE ###

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod + x % mod)% mod
n = int(input())
mod = 10**9 + 7
a = list(map(int,input().split()))
il = [[]for i in range(n)]
for i in range(n+1):
    il[a[i]-1].append(i)
    if len(il[a[i]-1]) > 1:
        p,q = il[a[i]-1]
comb = 1
comb2 = 1
c = p + n - q
for i in range(n+1):
    comb = (((comb*(n+1-i))%mod)*mod_inv(i+1,mod))%mod
    if c >= i:
        print((comb-comb2)%mod)
        comb2 = (((comb2*(c-i))%mod)*mod_inv(i+1,mod))%mod
    else:
        print(comb%mod)
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    query = list(input().split())
    if int(query[0])==1:
        s = s[::-1]
    elif int(query[0])==2:
        if int(query[1])==1:
            s = query[2] + s
        elif int(query[1])==2:
            s = s + query[2]

print(s)


### FIXED CODE ###

s = input()
q = int(input())
cnt = 0
left = ''
right = ''
for i in range(q):
    query = list(input().split())
    if int(query[0])==1:
        cnt += 1
    elif int(query[0])==2:
        if int(query[1])==1:
            if cnt%2==0:
                left = query[2] + left
            else:
                right = right + query[2]
        elif int(query[1])==2:
            if cnt%2==0:
                right = right + query[2]
            else:
                left = query[2] + left

if cnt%2==0:
    print(left+s+right)
else:
    s=left+s+right
    s=s[::-1]
    print(s)
### BUGGY CODE ###

S = input()
s = list(S)
Q = int(input())
p = [[0 for i in range(3)]for j in range(Q)]
x = 1
for i in range(Q):
    p[i] = list(map(str,input().split()))
def add(s,x,f,c):
    if x ==1:
        if f == 1:
            s.insert(0,str(c))
        else:
            s.append(str(c))
    else:
        if f == 1:
            s.append(str(c))
        else:
            s.insert(0,str(c))
for i in range(Q):
    if int(p[i][0]) == 1:
        x = -x
    else:
        add(s,x,int(p[i][1]),p[i][2])
if x == 1:
    print(''.join(s))
else:
    s.reverse()
    print(''.join(s))

### FIXED CODE ###

from collections import deque
S = input()
s = list(S)
d = deque()
for i in range(len(s)):
    d.append(s[i])
Q = int(input())
p = [[0 for i in range(3)]for j in range(Q)]
x = 1
for i in range(Q):
    p[i] = list(map(str,input().split()))
def add(s,x,f,c):
    if x ==1:
        if f == 1:
            s.appendleft(str(c))
        else:
            s.append(str(c))
    else:
        if f == 1:
            s.append(str(c))
        else:
            s.appendleft(str(c))
for i in range(Q):
    if int(p[i][0]) == 1:
        x = -x
    else:
        add(d,x,int(p[i][1]),p[i][2])
if x == 1:
    print(''.join(d))
else:
    d.reverse()
    print(''.join(d))
### BUGGY CODE ###

#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    S = input()
    # Slist = [input()]
    Q = II()
    # Slist = ['']*Q+Slist+['']*Q
    r = False
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            r ^= True
        else:
            if query[1] == '1':
                    if r:
                        S = ''.join([S,query[2]])
                    else:
                        S = ''.join([query[2],S])
            else:
                if r:
                    S = ''.join([query[2],S])
                else:
                    S = ''.join([S,query[2]])
    print(S[::-1] if r else S)
                



    

if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    S = input()
    Slist = [S]
    Q = II()
    Slist = ['']*Q+Slist+['']*Q
    left = Q-1
    right = Q+1
    r = False
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            r ^= True
        else:
            if query[1] == '1':
                    if r:
                        # S = ''.join([S,query[2]])
                        Slist[right] = query[2]
                        right += 1

                    else:
                        # S = ''.join([query[2],S])
                        Slist[left] = query[2]
                        left -=1
            else:
                if r:
                    Slist[left] = query[2]
                    left -=1
                else:
                    # S = ''.join([S,query[2]])
                    Slist[right] = query[2]
                    right += 1
    # print(S[::-1] if r else S)
    if r:
        Slist[Q] = Slist[Q][::-1]

    print(''.join(Slist[::-1]) if r else ''.join(Slist))
                



    

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

class EndLoop(Exception):
    pass


def solve():
    N = int(input())

    try:
        for h in range(1, 3500):
            for n in range(1, 3500):
                if 4 * h * n - n * N - h * N == 0:
                    pass
                elif (h * n * N) % (4 * h * n - n * N - h * N) == 0 and\
                            (4 * h * n - n * N - h * N) > 0:
                    w = (h * n * N) / (4 * h * n - n * N - h * N)
                    print(h, n, int(w))
                    raise EndLoop
    except(EndLoop):
        pass


solve()

### FIXED CODE ###

class EndLoop(Exception):
    pass


def solve():
    N = int(input())
    try:
        for h in range(1, 3501):
            for n in range(1, 3501):
                if 4 * h * n - n * N - h * N > 0:
                    if (h * n * N) % (4 * h * n - n * N - h * N) == 0:
                        w = int((h * n * N) / (4 * h * n - n * N - h * N))
                        print(h, n, int(w))
                        raise EndLoop
    except:
        pass


solve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
e = [[] for _ in range(n+1)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    e[v].append((u,(a,b)))
    e[u].append((v,(a,b)))


inf = 10**18
def dijkstra(s,cu):
    d = [inf]*(n+1)
    d[s] = 0
    q = [s]
    heapq.heapify(q)

    while len(q)>0:
        v = heapq.heappop(q)
        for u,ud in e[v]:
            if d[u]<=d[v]+ud[cu]:
                continue
            d[u] = d[v] + ud[cu]
            heapq.heappush(q, u)
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
res[n-1] = da[n]+db[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], da[i+1]+db[i+1])

for r in res:
    print(10**15 - r)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

for r in res:
    print(10**15-r)
### BUGGY CODE ###

import statistics
import copy

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

for i in range(len(X)):
    A = copy.deepcopy(X)
    del A[i]
    print(statistics.median(A))


### FIXED CODE ###

import statistics as sta

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

sort_X = sorted(X)
a = sta.median_low(sort_X)
b = sta.median_high(sort_X)

for i in range(N):
    if X[i] <= a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

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

total = 0
min_sekisan = 1
mod = 10 ** 9 + 7
for i in range(1, n):
    min_sekisan *= i
#print(min_sekisan)

counter = 0
iter = 0
for i in range(n-1):
    iter += 1
    counter += min_sekisan
    total -= (min_sekisan * X[i]) % mod
    min_sekisan *= iter
    min_sekisan //= iter + 1
total += (X[n-1] * counter) % mod
print(total % mod)

"""
from collections import defaultdict as dd
import copy
def count(n):
    lis = [[[i for i in range(1, n + 1)], dd(int)]]
    while len(lis[0][0]) != 1:
        temp = []
        for nums, counter in lis:
            for i in range(len(nums)-1):
                new_dic = copy.deepcopy(counter)
                new_dic[nums[i]] -= 1
                new_dic[nums[i+1]] += 1
                temp.append([nums[:i] + nums[i+1:], new_dic])
        lis = temp
    return lis
#print(count(4))
#print(len(count(4)))

total = dd(int)
for lis, dic in count(7):
    for key, val in dic.items():
        total[key] += val
print(total)
"""

### FIXED CODE ###

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

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

total = 0
min_sekisan = 1
mod = 10 ** 9 + 7
for i in range(1, n):
    min_sekisan *= i
    min_sekisan %= mod
#print(min_sekisan)

counter = 0
for i in range(n-1):
    counter += min_sekisan
    total -= (min_sekisan * X[i]) % mod
    min_sekisan *= i + 1
    min_sekisan *= mod_inv(i + 2, mod)
    min_sekisan %= mod
total += (X[n-1] * counter) % mod
print(total % mod)

"""
from collections import defaultdict as dd
import copy
def count(n):
    lis = [[[i for i in range(1, n + 1)], dd(int)]]
    while len(lis[0][0]) != 1:
        temp = []
        for nums, counter in lis:
            for i in range(len(nums)-1):
                new_dic = copy.deepcopy(counter)
                new_dic[nums[i]] -= 1
                new_dic[nums[i+1]] += 1
                temp.append([nums[:i] + nums[i+1:], new_dic])
        lis = temp
    return lis
#print(count(4))
#print(len(count(4)))

total = dd(int)
for lis, dic in count(7):
    for key, val in dic.items():
        total[key] += val
print(total)
"""
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())

edges = [set() for _ in range(N)]

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

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


step2 = [set() for _ in range(N)]

for u in range(N):
    for v in edges[u]:
        step2[u] |= edges[v]

cost = [-1 for _ in range(N)]
q = []
heapq.heappush(q, (0, S))

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for u2 in step2[u]:
        rms = set()
        for v in edges[u2]:
            if cost[v] != -1:
                rms.add(v)
            else:
                heapq.heappush(q, (c+1, v))

        edges[u2] -= rms

print(cost[T])


### FIXED CODE ###

import heapq
N, M = map(int, input().split())

edges = [set() for _ in range(N)]

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

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

cost = [-1 for _ in range(N)]
q = []
heapq.heappush(q, (0, S))

step1memo = set()
step2memo = set()
step3memo = set()

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for u1 in edges[u]:
        if u1 in step1memo:
            continue
        step1memo.add(u1)
        for u2 in edges[u1]:
            if u2 in step2memo:
                continue
            step2memo.add(u2)
            for u3 in edges[u2]:
                heapq.heappush(q, (c+1, u3))

print(cost[T])