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

n, m, r = list(map(int, input().split()))
rs = set(map(int, input().split()))
abcs = []
for _ in range(m):
    abcs.append(list(map(int, input().split())))

# construct graph
roads = [[] for _ in range(n + 1)]
for a, b, c in abcs:
    roads[a].append((b, c))
    roads[b].append((a, c))
# road from sky
for rr in rs:
    roads[0].append((rr, 0))

import heapq
import copy
# distance, town, rest-town-list, walked
Q = [(0, 0, rs, set())]
while len(Q) > 0:
    d, u, rest, walked = heapq.heappop(Q)
    if len(rest) == 0:
        ans = d
        break
    for v, dd in roads[u]:
        if (u, v) not in walked:
            heapq.heappush(Q, (d + dd, v, rest - {v}, walked | {(u, v)}))

print(ans)

### FIXED CODE ###

n, m, r = list(map(int, input().split()))
rs = list(map(int, input().split()))
# construct map
import numpy as np
dists = np.ones((n + 1, n + 1)) * float('inf')
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
for i in range(1, n + 1):
    dists[i, i] = 0

from itertools import product, permutations
for i, k in product(range(1, 1 + n), repeat=2):
    dists[:, k] = np.minimum(dists[:, k], dists[:, i] + dists[i, k])

ans = float('inf')
for path in permutations(rs):
    val = sum(dists[i, j] for i, j in zip(path, path[1:]))
    val = int(val)
    if val < ans:
        ans = val

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

N, K = map(int, input().split())
array = []

for i in range(N):
  a, b = map(int, input().split())
  array.extend([a]*b)
                
array.sort()

print(array[K- 1])

### FIXED CODE ###

N, K = map(int, input().split())
array = [0]*(10**5+ 1)

for i in range(N):
  a, b = map(int, input().split())
  array[a]+= b
  
S = 0
i = 0

while S < K:
  S+= array[i]
  i+= 1
  
print(i- 1)
### BUGGY CODE ###

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

for i in range(n):
    if(a[i] == 0):
        exit
if n % 2 == 0:
    for i in range(n//2):
        ans *= a[i]
        ans *= a[n-i-1]
elif n % 2 == 1:
    for i in range(n//2):
        ans *= a[i]
        ans *= a[n-i-1]
    ans *= a[n//2]

if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
a.sort()
if a[0] == 0:
    ans = 0
    print(ans)
    exit()

for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()

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

#!/usr/bin python3
# -*- coding: utf-8 -*-

n, k = map(int, input().split())
p = [int(i)-1 for i in input().split()]
c = list(map(int, input().split()))

ret = - 10 ** 18
for s in range(n):
    nxt = p[s]
    S = [c[nxt]]
    while nxt != s:
        nxt = p[nxt]
        S.append(S[-1]+c[nxt])

    if k<=len(S):
        pt = max(S[:k])
    else:
        if S[-1] <= 0:
            pt = max(S)
        else:
            pt = max(S)
            if k%len(S)!=0:
                pt = max(pt, S[-1]+max(S[:k%len(S)]))
            pt += S[-1]*(k//len(S)-1)
    ret = max(ret, pt)
print(ret)

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

n, k = map(int, input().split())
p = [int(i)-1 for i in input().split()]
c = list(map(int, input().split()))

ret = - 10 ** 18
for s in range(n):
    nxt = p[s]
    S = [c[nxt]]
    while nxt != s:
        nxt = p[nxt]
        S.append(S[-1]+c[nxt])

    if k<=len(S):
        pt = max(S[:k])
    else:
        if S[-1] <= 0:
            pt = max(S)
        else:
            pt = max(S)
            if k%len(S)!=0:
                pt = max(pt, S[-1]+max(S[:k%len(S)]))
            pt += S[-1]*(k//len(S)-1)
    ret = max(ret, pt)
print(ret)
### BUGGY CODE ###

N,K=map(int,input().split())
A=[]
for i in range(abs(N-K)+1):
    N=abs(N-K)
    A.append(N)
print(min(A))

### FIXED CODE ###

N,K=map(int,input().split())
R=N%K
print(min(abs(K-R),abs(R)))
### BUGGY CODE ###

def get_answer(s):
    count = 0
    for i, c in enumerate(s):
        if i == len(s) - 1:
            return count
        if c == "A" and s[i + 1] == "C":
            count += 1

    return count

n, q = map(int, input().split())
s = str(input())
questions = []
for _ in range(q):
    a, b = map(int, input().split())
    questions.append((a - 1, b - 1))

for question in questions:
    print(get_answer(s[question[0]: question[1] + 1]))


### FIXED CODE ###

def get_answer(a, start, end):
    return a[end] - a[start]

def create_answer_array(s):
    result = []
    result.append(0)

    for i in range(1, len(s)):
        if s[i - 1] == "A" and s[i] == "C":
            result.append(result[i - 1] + 1)
        else:
            result.append(result[i - 1])

    return result

n, q = map(int, input().split())
s = str(input())
questions = []
for _ in range(q):
    a, b = map(int, input().split())
    questions.append((a - 1, b - 1))

a = create_answer_array(s)

for question in questions:
    print(get_answer(a, question[0], question[1]))
### BUGGY CODE ###

import numpy as np

N, K = [int(i) for i in input().split()]
H = [int(h) for h in input().split()]

H = np.sort(np.array(H))[::-1]
for i in range(min(K, H.shape[0])):
    H = np.delete(H, 0)

print(np.sum(H))


### FIXED CODE ###

import numpy as np

N, K = [int(i) for i in input().split()]
H = [int(h) for h in input().split()]

H = np.sort(np.array(H))[::-1]
H = H[min(K, H.shape[0]):]

print(np.sum(H))
### BUGGY CODE ###

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

rewards = [None] * N
for i in range(N):
    a, b = map(int, input().split())
    rewards[i] = (b, a)

heap = []
total = 0
for day in range(1, M + 1):
    target_rewards = list(filter(lambda x: (day - 1) < x[1] <= day, rewards))

    for reward in target_rewards:
        heapq.heappush(heap, (-reward[0], reward[1]))

    if len(heap) > 0:
        max_reward = heapq.heappop(heap)
        total += -max_reward[0]

print(total)


### FIXED CODE ###

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

rewards = [[] for _ in range(M + 1)]
for i in range(N):
    a, b = map(int, input().split())
    if a <= M:
        rewards[a].append(b)

heap = []
total = 0
for day in range(1, M + 1):
    for reward in rewards[day]:
        heapq.heappush(heap, -reward)

    if len(heap) > 0:
        max_reward = heapq.heappop(heap)
        total += -max_reward

print(total)
### BUGGY CODE ###

K = int(input())

import itertools
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

lis = list(range(1,K+1))
S = [gcd_list(team) for team in itertools.product(lis, repeat = 3)]
print(sum(S))


### FIXED CODE ###

K = int(input())

import itertools
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

lis = list(range(1,K+1))
S = [gcd_list(team) for team in itertools.product(lis, repeat = 3)]

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

def main():
    import sys,heapq
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = {}
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x-0.5,x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if int(p[cnt][0]) == p[cnt][0]:
                if w in used:
                    used[w] += 1
                else:
                    used[w] = 1
                heapq.heappush(tank,w)
            else:
                used[w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = heapq.heappop(tank)
            if used[kouho] > 0:
                print(kouho)
                heapq.heappush(tank,kouho)
                break
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x,-x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if w>=0:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[-w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(tank)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力 <int> list[]
P = list(map(int, input().split()))

count = 0

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

print(count)


### FIXED CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力 <int> list[]
P = list(map(int, input().split()))

count = 0
comp = 2 * (10**5)

for i in range(N):
    if comp >= P[i]:
        count += 1
        comp = P[i]

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

n,m=list(map(int,input().split()))
a = [int(input()) for _ in range(m)]

pre2 = 0
pre1 = 0
cur = 1

for i in range(n):
    pre2 = pre1
    pre1 = cur 
    cur = pre1 + pre2
    if i+1 in a:
        cur = 0
    if cur == 0 and pre1 == 0:
        break
print(cur%1000000007)

### FIXED CODE ###

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

if n+1 < 2*m:
    print(0)
else:
    a = [int(input()) for _ in range(m)]

    pre2 = 0
    pre1 = 0
    cur = 1
    a_id = 0

    for i in range(n):
        pre2 = pre1
        pre1 = cur 
        cur = pre1 + pre2
        if a_id < m:
            if i+1 == a[a_id]:
                a_id += 1 if a_id < m-1 else 0
                cur = 0
        if cur == 0 and pre1 == 0:
            break
    print(cur%1000000007)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
from itertools import combinations

def main():
    X, Y, Z, K = map(int, readline().rstrip().split())
    A = list(map(int, readline().rstrip().split()))
    B = list(map(int, readline().rstrip().split()))
    C = list(map(int, readline().rstrip().split()))
    ab = []
    for a in A:
        for b in B:
            ab.append(a + b)
    ab = sorted(ab, reverse=True)[:K]
    abc = []
    for v in ab:
        for c in C:
            abc.append(v + c)
    
    print(*sorted(abc, reverse=True)[:K], sep='\n')


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    X, Y, Z, K = map(int, readline().rstrip().split())
    A = list(map(int, readline().rstrip().split()))
    B = list(map(int, readline().rstrip().split()))
    C = list(map(int, readline().rstrip().split()))
    
    ab = [A[i] + B[j] for i in range(len(A)) for j in range(len(B))]
    ab = sorted(ab, reverse=True)[:K]

    abc = [ab[i] + C[j] for i in range(len(ab)) for j in range(len(C))]
    print(*sorted(abc, reverse=True)[:K], sep='\n')


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

import sys
sys.setrecursionlimit(10**9)

def dfs1(v):
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      g2[v].append(u)
      g3[v].append(u)
      g3[u].append(v)
      dfs1(u)
      
def dfs2(v):
  for u in g2[v]:
    if checked[u]==0:
      checked[u]=1
      dfs2(u)
      if cnt[u]%2==1:
        ans.append((u,v))
        cnt[u]+=1
      else:
        ans.append((v,u))
        cnt[v]+=1
      
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
g2=[[] for _ in range(n+1)]
g3=[[] for _ in range(n+1)]
cnt=[0]*(n+1)
ans=[]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
if m%2==1:
  print(-1)
else:
  checked=[0]*(n+1)
  checked[1]=1
  dfs1(1)
  for v in range(1,n+1):
    for u in g[v]:
      if u not in g3[v]:
        if (u,v) not in ans:
          ans.append((v,u))
          cnt[v]+=1
  checked=[0]*(n+1)
  checked[1]=1
  dfs2(1)
  for v,u in ans:
    print(v,u)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def dfs1(v):
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      g2[v].append(u)
      g3[v].append(u)
      g3[u].append(v)
      dfs1(u)
      
def dfs2(v):
  for u in g2[v]:
    if checked[u]==0:
      checked[u]=1
      dfs2(u)
      if cnt[u]%2==1:
        ans.append((u,v))
        cnt[u]+=1
      else:
        ans.append((v,u))
        cnt[v]+=1
      
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
g2=[[] for _ in range(n+1)]
g3=[[] for _ in range(n+1)]
cnt=[0]*(n+1)
ans=[]
ansset=set()
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
if m%2==1:
  print(-1)
else:
  checked=[0]*(n+1)
  checked[1]=1
  dfs1(1)
  for v in range(1,n+1):
    for u in g[v]:
      if u not in g3[v]:
        if (u,v) not in ansset:
          ans.append((v,u))
          ansset.add((v,u))
          cnt[v]+=1
  checked=[0]*(n+1)
  checked[1]=1
  dfs2(1)
  for v,u in ans:
    print(v,u)
### BUGGY CODE ###

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

def calc_comb(lst_A):

    elem_A = list(set(lst_A))
    sum_comb = 0
    dct_A = {}

    for A in elem_A:
        numA  = lst_A.count(A)
        combA = (numA * (numA-1)) // 2
        dct_A[A] = numA
        sum_comb += combA

    return sum_comb, dct_A



def main(N, lst_A):

    sum_comb_all, dct_A = calc_comb(lst_A)
    lst_sum_comb = []

    for A in lst_A:
        numA = dct_A[A]
        prev_combA = (numA * (numA-1)) // 2
        new_combA  = ((numA-1) * (numA-2)) // 2

        sum_comb = sum_comb_all - prev_combA + new_combA
        lst_sum_comb.append(sum_comb)

    return lst_sum_comb

if __name__ == "__main__":

    lst_answer = main(N, lst_A)
    for answer in lst_answer:
        print(answer)
    

### FIXED CODE ###

from collections import Counter

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

def main(N, lst_A):

    dct_cntA = Counter(lst_A)
    sum_comb = 0

    for cntA in dct_cntA.values():
        comb = (cntA * (cntA - 1)) // 2
        sum_comb += comb

    for A in lst_A:
        print(sum_comb - (dct_cntA[A] - 1))

    return 0

if __name__ == "__main__":

    main(N, lst_A)
### BUGGY CODE ###

import heapq 
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    l[i][0],l[i][1]=-l[i][0],-l[i][1]
heapq.heapify(l)
ans=0
for i in range(n):
    ans-=l[0][0]*((-1)**i)
    minimum=heapq.heappop(l)
    for j in range(n-i-1):
        l[j][0],l[j][1]=l[j][1],l[j][0]
    #print(l)
print(ans)



### FIXED CODE ###

n=int(input())
l=[]
c=0
for i in range(n):
    a,b=map(int,input().split())
    c-=b
    l.append(a+b)
l.sort()
l=l[::-1]
for i in range(0,n,2):
    c+=l[i]
print(c)
### BUGGY CODE ###

from heapq import heappop,heappush,heapify
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int (i) for i in input().split()]
heapify(A)
D = []
P = 0
for i in range(M):
  B,C = map(int, input().split())
  D.extend([C]*B)
  P += B
D.sort(reverse=True)
for i in range(P):
  if A[0] < D[i]:
    x = heappop(A)
    heappush(A,D[i])
  else:
    break
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)
### BUGGY CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n) + 1
    l = [0] + [1] * (n - 1)
    c = 2
    while c < mx:

        for k in range(2, floor(n/c) + 1):
            l[c * k -1] = 0
        c = l[:c].index(1) + c
    return sum(l)
for n in stdin:
    n = int(n)
    print(cntPrime(n))

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
### BUGGY CODE ###

N = int(input())
answer = 1
for i in range(N) :
    answer *= (i+1)
answer = answer % (10**9+7)
print(answer)


### FIXED CODE ###

N = int(input())
answer = 1
for i in range(N) :
    answer = (answer*(i+1))%(10**9+7)
print(answer)
### BUGGY CODE ###

N=int(input())

import numpy as np
seq=np.array([])

for i in range(N):

    a= int(input())
    
    seq=np.append(seq,a)

index=np.argsort(seq)[::-1]
for j in range(N):
    if index[0]==j:
        print(int(seq[index[1]]))
    else:
        print(int(seq[index[0]]))


### FIXED CODE ###

N=int(input())

seq=[]

for i in range(N):
    a= int(input())
    seq.append(a)

import heapq

tmp=list(map(lambda x: x*(-1),seq))
heapq.heapify(tmp)

a=heapq.heappop(tmp)*(-1)
b=heapq.heappop(tmp)*(-1)

for j in range(N):
    if seq[j]==a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

N = int(input())
S = list(input())

while True:
    count = 0
    for i in range(len(S) - 1):
        if S[i] == S[i + 1]:
            S.pop(i)
            count += 1
            break
    if count == 0:
        break

print(len(S))

### FIXED CODE ###

import itertools

N = int(input())
S = list(input())

print(len([k for k, v in itertools.groupby(S)]))
### BUGGY CODE ###

import itertools
def list_difference(list1, list2):
    result = list1.copy()
    for value in list2:
        if value in result:
            result.remove(value)

    return len(result)


n=int(input())
a=[list(input()) for i in range(n)]
count=0
a=list(itertools.combinations(a,2))
for i in range(len(a)):
    if list_difference(a[i][0],a[i][1])==0:
        count+=1
print(count)

### FIXED CODE ###

import math
import collections

n=int(input())
a=[list(input()) for i in range(n)]
b=[str(sorted(list(i))) for i in a]
count=list(collections.Counter(b).values())
count=[i for i in count if i>1]
print(int(sum([math.factorial(x)/(math.factorial(x-2)*2) for x in count])))
### BUGGY CODE ###

s = input()
t = input()

ls,lt = len(s),len(t)
dp = [[(0,"")]*(lt+1) for _ in [0]*(ls+1)]
for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = [dp[i-1][j][0]+1,dp[i-1][j][1]+s[i-1]]
        elif dp[i-1][j][0] >= dp[i][j-1][0]:
            dp[i][j] = dp[i-1][j][:]
        else:
            dp[i][j] = dp[i][j-1][:]
print(dp[-1][-1][1])

### FIXED CODE ###

s = input()
t = input()

ls,lt = len(s),len(t)
dp = [[0]*(lt+1) for _ in [0]*(ls+1)]

for i,cs in enumerate(s,1):
    for j,ct in enumerate(t,1):
        if cs==ct:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

i = ls
j = lt
ans = ""
while i>0 and j>0:
    if s[i-1] == t[j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -=1
        else:
            j -=1
print(ans[::-1])
### BUGGY CODE ###

import collections
import numpy as np

# リストarrからx個の同じ長さの列を取り出す時の最大の長さ
# 発想: x個取り出す時、ある文字をx個より多く取り出して列に含むことはない
#       一方ある文字をその文字がある数よりも取り出して使うこともできない
#       つまり、min(arr.count(a), x)で、x個の同じ長さの列に使えるaの数がわかる
#       さらに、sum(min(arr.count(a),x))で、x個の同じ長さの列に使える文字の数がわかる
#       よって、sum(min(arr.count(a),x))//xで、x個の同じ長さの列の長さがわかる
#       発展的に、longest(arr,x)までの計算状況からlongest(arr,x+1)が計算できる
def longest(arr, x):    # legacy
    return sum(min(arr.count(a), x) for a in arr) // x


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

nums = list(collections.Counter(a).values())
lastest_add = np.count_nonzero(nums)
building = [0]
longests = [0]
for i in range(1, n+1):
    appended = building[-1] + lastest_add
    building.append(appended)
    longests.append(appended // i)
    lastest_add -= nums.count(i)

for k in range(1, n+1):
    maxindexes = list(i for i, x in enumerate(longests) if x >= k)
    if maxindexes:
        print(max(maxindexes))
    else:
        print(0)
    


### FIXED CODE ###

import collections
import numpy as np

# リストarrからx個の同じ長さの列を取り出す時の最大の長さ
# 発想: x個取り出す時、ある文字をx個より多く取り出して列に含むことはない
#       一方ある文字をその文字がある数よりも取り出して使うこともできない
#       つまり、min(arr.count(a), x)で、x個の同じ長さの列に使えるaの数がわかる
#       さらに、sum(min(arr.count(a),x))で、x個の同じ長さの列に使える文字の数がわかる
#       よって、sum(min(arr.count(a),x))//xで、x個の同じ長さの列の長さがわかる
#       発展的に、longest(arr,x)までの計算状況からlongest(arr,x+1)が計算できる
# def longest(arr, x):    # legacy
#     return sum(min(arr.count(a), x) for a in arr) // x


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

counter = collections.Counter(a)        #O(n)
nums = list(counter.values())           #O(n)
num_counter = collections.Counter(nums) #O(n)
lastest_add = np.count_nonzero(nums)    #O(n)
building, longests = [0], [0]
for i in range(1, n+1):                 #O(n)
    appended = building[-1] + lastest_add   #O(1)
    building.append(appended)               #O(1)
    longests.append(appended // i)          #O(1)
    lastest_add -= num_counter[i]           #O(1)


lastest_longest = 0
k_most = []
for i, x in enumerate(reversed(longests)):
    while x > lastest_longest:
        lastest_longest += 1
        k_most.append(n-i)

k_most.extend([0]*(n-len(k_most)))      # zero padding

for longests_num in k_most:
    print(longests_num)

# print('----------------')
# for k in range(1, n+1):
#     maxindexes = list(i for i, x in enumerate(longests) if x >= k)
#     if maxindexes:
#         print(maxindexes[-1])
#     else:
#         print(0)
### BUGGY CODE ###

import heapq
from collections import deque

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

dic = {}

for i in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []

    dic[u].append(v)


far = [[float("inf")] * 3 for i in range(N)]
nend = [ [True] * 3 for i in range(N) ]

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

q = deque([])
q.append([0,S])

while len(q) > 0:

    now = q.popleft()

    nd = now[0]
    np = now[1]
    nend[np][nd % 3] = False

    far[np][nd % 3] = min(far[np][nd % 3],nd)

    if np in dic:
        for i in dic[np]:

            if nend[i][(nd + 1) % 3] and far[i][(nd+1)%3] > far[np][nd%3] + 1:
                q.append([nd + 1 , i])

if far[T][0] == float("inf"):
    print (-1)
else:
    print (far[T][0] // 3)
    


### FIXED CODE ###

import heapq
from collections import deque

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

dic = {}

for i in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []

    dic[u].append(v)


far = [[float("inf")] * 3 for i in range(N)]
nend = [ [True] * 3 for i in range(N) ]

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

q = deque([])
q.append([0,S])

while len(q) > 0:

    now = q.popleft()

    nd = now[0]
    np = now[1]
    nend[np][nd % 3] = False

    far[np][nd % 3] = min(far[np][nd % 3],nd)

    if np in dic:
        for i in dic[np]:

            if nend[i][(nd + 1) % 3] and far[i][(nd+1)%3] > far[np][nd%3] + 1:
                q.append([nd + 1 , i])
                nend[i][(nd+1)%3] = False

if far[T][0] == float("inf"):
    print (-1)
else:
    print (far[T][0] // 3)