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

N, Q = map(int, input().split())
s = str(input())
coms = [list(map(str, input().split())) for _ in range(Q)]

def ok_lower(A, index, coms):
    # シミュレーションを行う
    for com in coms:
        if com[0] == A[index]:
            if com[1] == 'R':
                index += 1
            elif com[1] == 'L':
                index -= 1
        if index == len(A):
            return True
        elif index == -1:
            return False
    return False


def ok_upper(A, index, coms):
    # シミュレーションを行う
    for com in coms:
        if com[0] == A[index]:
            if com[1] == 'R':
                index += 1
            elif com[1] == 'L':
                index -= 1
        if index == len(A):
            return False
        elif index == -1:
            return True
    return False


def lower_bound(A, coms):
    ng = -1
    ok = len(A)

    while(abs(ok-ng) > 1):
        mid = (ok + ng) // 2

        if ok_lower(A, mid, coms):
            ok = mid
        else:
            ng = mid
    return ok


def upper_bound(A, coms):
    ng = len(A)
    ok = -1

    while(abs(ok-ng) > 1):
        mid = (ok + ng) // 2

        if ok_upper(A, mid, coms):
            ok = mid
        else:
            ng = mid
    return ok


lower = lower_bound(s, coms)
upper = upper_bound(s, coms)
print(max(0, lower-upper-1))

### FIXED CODE ###

N, Q = map(int, input().split())
s = str(input())
coms = [list(map(str, input().split())) for _ in range(Q)]


def isOK(A, index, coms, c):
    # シミュレーションを行う
    for com in coms:
        if com[0] == A[index]:
            if com[1] == 'R':
                index += 1
                if index == len(A):
                    return c == 'R'
            elif com[1] == 'L':
                index -= 1
                if index == -1:
                    return c == 'L'
    return False


def lower_bound(A, coms):
    ng = -1
    ok = len(A)

    while(abs(ok-ng) > 1):
        mid = (ok + ng) // 2

        if isOK(A, mid, coms, 'R'):
            ok = mid
        else:
            ng = mid
    return ok


def upper_bound(A, coms):
    ng = len(A)
    ok = -1

    while(abs(ok-ng) > 1):
        mid = (ok + ng) // 2

        if isOK(A, mid, coms, 'L'):
            ok = mid
        else:
            ng = mid
    return ok


lower = lower_bound(s, coms)
upper = upper_bound(s, coms)
print(lower-upper-1)
### BUGGY CODE ###

X = int(input())
dist = [0]
prev_dist = [0]
time = 0
while not X in dist:
    time += 1
    for i in prev_dist:
        if not i+time in dist: dist.append(i+time)
        if not i-time in dist: dist.append(i-time)
    prev_dist = dist[:]
print(time)

### FIXED CODE ###

X = int(input())
for i in range(X+1):
    if (i*(i+1)/2) >= X:
        time = i
        break
print(time)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main2(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

    knapsack_dp = [[0 for _ in range(W+1)] for _ in range(N)]

    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

    print(knapsack_dp[N-1][W])

def main():
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

    knapsack_dp = [[0 for _ in range(W+1)] for _ in range(N)]

    # knapsack_dp[考慮した品物][その重さピッタリの重さ] = 価値 とする。
    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight != w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

    print(max(knapsack_dp[N-1]))

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, W = LI()
    wv = []
    for _ in range(N):
        wv.append(LI())


    # 横軸 v, 縦軸 n
    dp_table = [[None for _ in range(10**5+1)] for _ in range(N)]
    
    # init
    w0, v0 = wv[0]
    dp_table[0][0] = 0
    dp_table[0][v0] = w0

    # dp
    for i, item in enumerate(wv):
        if i== 0: continue
        w,v = item
        for val, weight in enumerate(dp_table[i-1]):
            if weight is not None:
                # i番目の荷物を入れないとき
                dp_table[i][val] = min(dp_table[i][val], weight) if dp_table[i][val] is not None else weight
                # i番目の荷物を入れるとき
                dp_table[i][val+v] = weight + w

    v  = 10**5
    for w in reversed(dp_table[N-1]):
        if w and w <= W:
            print(v)
            break
        v -= 1


main()
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, min(k, n - i - 1) + 1):
            dp[i + j] = min(
                dp[i + j],
                dp[i] + abs(h[i] - h[i + j]) )
    print(int(dp[-1]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np


def main():
    n, k = map(int, input().split())
    height = np.fromstring(input(), 'int32', sep=' ')
    height = np.append(height, [0] * (k - 1))

    dp = np.full((n + k - 1), 10 ** 9, dtype='int')
    dp[0] = 0

    for i in range(n - 1):
        default_val = dp[i + 1:i + 1 + k]
        new_val = dp[i] + np.abs(height[i + 1:i + 1 + k] - height[i])
        dp[i + 1:i + 1 + k] = np.minimum(default_val, new_val)
    print(dp[n - 1])


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

import heapq

N, K = map(int, input().split())
A = list(map(int, input().split()))
set_A = set(A)
len_types = len(set_A)
memo = []
ans = 0

for num in set_A:
    count_num = A.count(num)
    heapq.heappush(memo, count_num)

while len_types > K:
    ans += heapq.heappop(memo)
    len_types -= 1

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
memo = [0] * N
ans = 0

for a in A:
    memo[a-1] += 1
    
memo.sort()

for i in memo[:N-K]:
    ans += i

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

n = int(input())
ls = [int(input()) for _ in range(n)]

p = []
for i, x in enumerate(ls):
    if i+1 != len(ls):
        p.append(max(ls[i+1:])-x)

print(max(p))


### FIXED CODE ###

n = int(input())
m = [int(input()) for _ in range(n)]

def fx(raw):
    min_n = raw[0]
    max_n = raw[1] - raw[0]
    for i in raw[1:]:
        if i - min_n >= max_n:
            max_n = i - min_n
        if i < min_n:
            min_n = i
    return max_n


if __name__ == '__main__':
    print(fx(m))
### BUGGY CODE ###

import numpy as np
h, n = map(int, input().split())
dp = np.zeros((n+1, h+1))
dp[0] = np.inf
for i in range(1, n+1):
    a, b = map(int, input().split())
    for j in range(1, h+1):
        if j >= a:
            dp[i][j] = min(
                dp[i-1][j], dp[i][j-a] + b,
            )
        else:
            dp[i][j] = min(
                dp[i-1][j], b
            )
print(int(dp[n][h]))


### FIXED CODE ###

h, n = map(int, input().split())
inf = 10**11

# dp[i]: 体力iを減らす魔力の最小値
dp = [inf] * 20000
dp[0] = 0

for _ in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        dp[j+a] = min(dp[j] + b, dp[j+a])

print(min(dp[h:]))
### BUGGY CODE ###

n = int(input())
h = 0
while(n > 4):
  if n >= 500:
    h += 1000
  elif n >= 5:
    h += 5
    
print(h)

### FIXED CODE ###

n = int(input())
h = 0
while(n > 4):
    if n >= 500:
        h += 1000
        n -= 500
    elif n >= 5:
        h += 5
        n -= 5
    

    
print(h)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
A.sort()
check = [0]*(max(A)+1)
for a in A:
    i = 1
    while a * i <= max(A):
        check[a*i] += 1
        i += 1
cnt = 0
for a in A:
    if check[a] == 1: cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
A.sort()

cnt = [0] * (10**6+1)
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for i in range(10**6+1)[a::a]:
        cnt[i] += 1
ans = 0
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###


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

RD = []
end = [False] * N

for i in range(N):

    RD.append([])

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q = [endp] 


        while len(Q) > 0:

            q = Q.pop(0)
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    ans = "No"
                    break

            if ans == "No":
                break

        if ans == "No":
            break

print (ans)


### FIXED CODE ###

from collections import deque

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

RD = [deque() for i in range(N)]
end = [False] * N

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = deque()

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)


        while len(Q) > 0:

            q = Q.pop()
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


print ("Yes")
### BUGGY CODE ###

N = int(raw_input())
m = {}
for i in range(N):
  ti = int(raw_input())
  pi = {}
  x = 2
  while x*x <= ti:
    while ti % x == 0:
      ti /= x
      pi[x] = pi.get(x,0)+1
    x += 1
  if ti > 1:
    pi[ti] = pi.get(ti,0)+1
  for x in pi.keys():
    m[x] = max(m.get(x,0), pi[x])
ret = 1
for x in m.keys():
  ret *= x**m[x]
print ret

### FIXED CODE ###

def gcd(a, b):
  m = max(a, b)
  n = min(a, b)
  if n==0:
    return m
  else:
    return gcd(n, m%n)
 
N = int(input())
l = 1
for i in range(N):
  t = int(input())
  g = gcd(l, t)
  l *= t//g
print(l)
### BUGGY CODE ###

class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    fr, br = [[] for _ in range(n + 1)], [[] for _ in range(n + 1)]
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        fr[a].append(b)
        fr[b].append(a)
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: i for i, k in enumerate(set(uf.t[1:]))}
    g = [[] for _ in enumerate(mp.keys())]
    for i in range(n + 1):
        if uf.t[i] > 0:
            g[mp[uf.t[i]]].append(i)
    for c, d in zip(*[iter(cd)] * 2):
        br[c].append(d)
        br[d].append(c)

    *fr, = map(set, fr)
    *br, = map(set, br)
    *g, = map(set, g)
    return " ".join([str(len(g[mp[uf.t[i]]] - fr[i] - br[i] - set([i]))) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    fr, br = [[] for _ in range(n + 1)], [[] for _ in range(n + 1)]
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        fr[a].append(b)
        fr[b].append(a)
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: i for i, k in enumerate(set(uf.t[1:]))}
    g = [[] for _ in enumerate(mp.keys())]
    for i in range(n + 1):
        if uf.t[i] > 0:
            g[mp[uf.t[i]]].append(i)
    for c, d in zip(*[iter(cd)] * 2):
        br[c].append(d)
        br[d].append(c)

    *fr, = map(len, fr)
    *g, = map(set, g)
    *gn, = map(len, g)
    return " ".join([
        str(gn[mp[uf.t[i]]] - 1 - fr[i] - sum(j in g[mp[uf.t[i]]]
                                              for j in br[i]))
        for i in range(1, n + 1)
    ])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

n,m=map(int,input().split())
A=[[0]*m for i in range(n)]
for i in range(n):
  A[i]=list(map(int,input().split()))
B=[0]*m
for i in range(n):
  B[A[i][0]-1]+=1
a=0
b=0
for i in range(m):
  if B[i]>a:
    a=B[i]
    b=i
ans=a
C=[b+1]
i=0
while i<=m-2:
  B=[0]*m
  for j in range(n):
    for k in range(m):
      if A[j][k] not in C:
        B[A[j][k]-1]+=1
        break
  a=0
  b=0
  for l in range(m):
    if B[l]>a:
      a=B[l]
      b=l
  if ans>a:
    ans=a
  C.append(b+1)
  i=i+1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
A=[[0]*m for i in range(n)]
for i in range(n):
  A[i]=list(map(int,input().split()))
B=[0]*m
for i in range(n):
  B[A[i][0]-1]+=1
a=0
b=0
for i in range(m):
  if B[i]>a:
    a=B[i]
    b=i
ans=a
C=[b+1]
i=0
while i<=m-2:
  B=[0]*m
  for j in range(n):
    for k in range(m):
      if A[j][k] not in C:
        B[A[j][k]-1]+=1
        break
  a=0
  b=0
  for l in range(m):
    if B[l]>a:
      a=B[l]
      b=l
  if ans>a:
    ans=a
  C.append(b+1)
  i=i+1
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
Y = [0] * Q
Task = [0] * Q

state = 1 # 反転していたら-1
for i in range(Q):
    q = input()
    if q == '1':
        state *= -1
    else:
        Y, f, c = q.split()
        if (state == 1 and f == '1') or (state == -1 and f == '2'):
            S = c + S
        elif (state == 1 and f == '2') or (state == -1 and f == '1'):
            S = S + c

if state == -1:
    S = S[::-1]
print(S)


### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())

state = 1 # 反転していたら-1
Stock = deque([S])
for i in range(Q):
    q = input()
    if q == '1':
        state *= -1
    else:
        Y, f, c = q.split()
        if (state == 1 and f == '1') or (state == -1 and f == '2'):
            Stock.appendleft(c)
        elif (state == 1 and f == '2') or (state == -1 and f == '1'):
            Stock.append(c)
S = ''.join(Stock)
if state == -1:
    S = S[::-1]
print(S)
### BUGGY CODE ###

K = int(input())
count = 1
check = 7

if K % 2 == 0 or K % 5 == 0:
    print(-1)
else:
    while True:
        if check % K == 0:
            print(count)
            break
        else:
            count += 1
            check = check * 10 + 7


### FIXED CODE ###

K = int(input())
count = 1
check = 7

if K % 2 == 0 or K % 5 == 0:
    print(-1)
else:
    while True:
        if check % K == 0:
            print(count)
            break
        else:
            count += 1
            check = (check * 10 + 7) % K
### BUGGY CODE ###

import bisect

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

x = []

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.insert(0, a)
        else:
            x[r - 1] = a

print(len(x))


### FIXED CODE ###

import bisect
import  collections

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

x = collections.deque()

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.appendleft(a)
        else:
            x[r - 1] = a

print(len(x))
### BUGGY CODE ###

n=int(input())
k=0
for i in range(n):
    while (i+1)**2 < n:
        k+=1
print((k+1)**2)

### FIXED CODE ###

n=int(input())
print((int(n**0.5))**2)
### BUGGY CODE ###

import copy
n = int(input())
a = [int(input()) for i in range(n)]
a_max = max(a)
for i in range(n):
    if a_max == a[i]:
        a_ = copy.deepcopy(a)
        del a_[i]
        print(max(a_))
    else:
        print(a_max)


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_sorted = sorted(a)
a_max = a_sorted[-1]
a_sec = a_sorted[-2]
for i in range(n):
    if a_max == a[i]:
        print(a_sec)
    else:
        print(a_max)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

n, m, k = map(int, input().split())
L = UnionFind(n)
F = [0] * n
B = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a] += 1
    F[b] += 1
    L.union(a, b)

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if L.same(c, d):
        B[c] += 1
        B[d] += 1

for i in range(n):
    print(L.size(i) - F[i] - B[i] - 1)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

n, m, k = map(int, input().split())
L = UnionFind(n)
F = [0] * n
B = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a] += 1
    F[b] += 1
    L.union(a, b)

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if L.same(c, d):
        B[c] += 1
        B[d] += 1

for i in range(n):
    print(L.size(i) - F[i] - B[i] - 1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt=1
for i in range(1,n):
  j = i-1;flag=0
  #print(i)
  while j>=0:
    if a[i]>a[j]:
      flag=1
      break
    j-=1
  if flag==0:
    cnt+=1
    
print(cnt)
  

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt=1;small=a[0]
for i in range(1,n):
  if a[i]<=small:
    #print(a[i],'--',large)
    cnt+=1
    small=a[i]
    
print(cnt)
### BUGGY CODE ###

from collections import defaultdict
from queue import Queue

n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
dist = [[MX, MX, MX] for i in range(n)]
reached = [[False, False, False] for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s][0] = 0

q = Queue()
q.put((s, 0))
while not q.empty():
    node, step = q.get()
    next_step = (step + 1) % 3
    reached[node][step] = True
    for next_node in edge[node]:
        if reached[next_node][next_step]: continue
        q.put((next_node, next_step))
        if step == 2:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step] + 1)
        else:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step])

if dist[t][0] == MX:
    print(-1)
else:
    print(dist[t][0])



### FIXED CODE ###

from collections import defaultdict
from queue import Queue

n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
dist = [[MX, MX, MX] for i in range(n)]
reached = [[False, False, False] for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s][0] = 0

q = Queue()
q.put((s, 0))
while not q.empty():
    node, step = q.get()
    next_step = (step + 1) % 3
    for next_node in edge[node]:
        if reached[next_node][next_step]: continue
        q.put((next_node, next_step))
        reached[next_node][next_step] = True
        if step == 2:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step] + 1)
        else:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step])

if dist[t][0] == MX:
    print(-1)
else:
    print(dist[t][0])
### BUGGY CODE ###

import sys

N, Y = map(int, input().split())
max1000 = int(Y/1000)
max5000 = int(max1000 / 5)
max10000 = int(max1000 / 10)
c1000 = [i for i in range(max1000, 0, -5) if i <= N]
c1000.append(0)
c5000 = [i for i in range(max5000, -1, -1) if i <= N]
c10000 = [i for i in range(max10000, -1, -1) if i <= N]
for i in c10000:
    for j in c5000:
        for k in c1000:
            if i+j+k == N:
                if i*10000 + j*5000 + k*1000 == Y:
                    print(str(i) + ' ' + str(j) + ' ' + str(k))
                    sys.exit()
print("-1 -1 -1")

### FIXED CODE ###


import sys

N, Y = map(int, input().split())
max1000 = int(Y/1000)
c1000 = [i for i in range(max1000, -1, -5) if i <= N]
for z in c1000:
    max5000 = int((max1000-z) / 5)
    for y in range(0, max5000+1):
        x = N - y - z
        if x*10000 + y*5000 + z*1000 == Y:
            print(str(x) + ' ' + str(y) + ' ' + str(z))
            sys.exit()
print("-1 -1 -1")