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

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N)]

for i in range(N):
    for j in range(W + 1):
        dp[i][j] = max(dp[i][j], dp[i - 1][j])
        if j >= wv[i][0]:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - wv[i][0]] + wv[i][1])
print(dp[N - 1][W])

### FIXED CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(1, N + 1):
    for j in range(W):
        w = wv[i - 1][0]
        v = wv[i - 1][1]
        if j + w <= W:
            dp[i][j + w] = max(dp[i][j + w], dp[i - 1][j] + v)
        dp[i][j] = max(dp[i][j], dp[i - 1][j])
        
print(max(dp[-1]))
### BUGGY CODE ###

import numpy as np

N = input()
a=(map(int, raw_input().split()))

b=np.array([]).astype(int)

for i in range(N):
    b=np.append(b, [a[i]])
    b=b[-1::-1]

print ''.join(str(b))[1:-1]


### FIXED CODE ###

N = input()
a=(map(str, raw_input().split()))

odd=a[1::2]
even=a[0::2]

if N%2==0:
    print ' '.join(reversed(odd))+' '+' '.join(even)
else:
    print ' '.join(reversed(even))+' '+' '.join(odd)
### BUGGY CODE ###

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

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

ans = 0

for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        m = [[-1] * W for _ in range(H)]

        q = deque()
        q.append((j, i, 0))

        while q:
            y, x, v = q.popleft()
            m[y][x] = v
            for d in ((y, x + 1), (y, x-1), (y+1, x), (y-1, x)):
                dj = d[0]
                di = d[1]
                if 0 <= dj < H and 0 <= di < W and m[dj][di] == -1 and S[dj][di] == ".":
                    q.append((dj, di, v+1))
                    if ans < v+1:
                        ans = v+1
print(ans)


### FIXED CODE ###

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

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0

        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)
### BUGGY CODE ###

a,b = map(int,input().split())
import math
def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0 and is_prime(i) == True:
            cf.append(i)
    return cf

def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

cf = cf(a,b)
print(len(cf) + 1)


### FIXED CODE ###

a,b = map(int,input().split())
import fractions
import collections
import copy
def prime_factorization(n):
    a = [1]
    n1 = copy.deepcopy(n)
    while n % 2 == 0:
        n //= 2
    if n1 != n:
        a.append(2)
    f = 3
    while f * f <= n:
        if n % f == 0:
            n //= f
            if a[-1] != f:
                a.append(f)
        else:
            f += 2
    if a[-1] != n and n != 1:
        a.append(n)
    return a
print(len(prime_factorization(fractions.gcd(a,b))))
### BUGGY CODE ###

import sys
from pprint import pprint

def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2) % (10**9 + 7)
    else:
        return (x * pow_r(x ** 2, (n - 1) // 2)) % (10**9 + 7)


def solve(n, a):

    zero_count = [0] * 60
    for a_i in a:
        binary = format(a_i, '060b')

        for j, b_j in enumerate(binary):
            zero_count[j] += int(b_j)

    ans = 0
    for i, count in enumerate(zero_count[::-1]):
        # ans += (2**i) * (count * (n - count)) 
        ans += pow_r(2, i) * (count * (n - count)) 
        ans %= 10**9 + 7
    print(ans)

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    a = map(int, sys.stdin.readline().strip().split(" "))
    
    solve(n, a)

### FIXED CODE ###

import sys
from pprint import pprint

mod = 10**9 + 7

def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2) % mod
    else:
        return (x * pow_r(x ** 2, (n - 1) // 2)) % mod


def solve(n, a):

    zero_count = [0] * 60
    for a_i in a:
        # binary = format(a_i, '060b')
        # for j, b_j in enumerate(binary):
        #    zero_count[j] += int(b_j)
        for j in range(61):
            if a_i >> j & 1:
                zero_count[j] += 1

    ans = 0
    # for i, count in enumerate(zero_count[::-1]):
    for i, count in enumerate(zero_count):
        # ans += (2**i) * (count * (n - count)) 
        ans += pow_r(2, i) * (count % mod) * ((n - count) % mod) 
        ans %= mod
    print(ans)

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    a = map(int, sys.stdin.readline().strip().split(" "))
    
    solve(n, a)
### BUGGY CODE ###

n,k = map(int, input().split())
link = [[] for _ in range(n)]
ln = []
for i in range(n-1):
    a,b = list(map(int,input().split()))
    link[a-1].append(b-1)
    link[b-1].append(a-1)
    ln.append([a-1,b-1])

if k==1:
    print(n-2)
    exit()

from collections import deque
def get_v(node,dist):
    Q = deque()
    Q.append([node,0])
    visited=[-1]*n
    visited[node]=1
    while Q:
        now,cnt = Q.popleft()
        if cnt > dist:
            break
        for nxt in link[now]:
            if visited[nxt]!=-1:
                continue
            visited[nxt]=cnt+1
            Q.append([nxt,cnt+1])
    for i in range(n):
        if visited[i] == -1:
            ret = 0
        elif visited[i] <= dist:
            ret = 1
        else:
            ret = 0
        visited[i] = ret
    return visited

import numpy as np
ans=float("inf")
if k%2==0:
    for i in range(n):
        ret = n - sum(get_v(i,k//2))
        ans=min(ret,ans)
else:
    for tmp in ln:
        n1,n2=tmp
        c1=np.array(get_v(n1,k//2))
        c2=np.array(get_v(n2,k//2))
        ret = n- sum(c1 | c2)
        ans=min(ret,ans)

print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
link = [[] for _ in range(n)]
ln = []
for i in range(n-1):
    a,b = list(map(int,input().split()))
    link[a-1].append(b-1)
    link[b-1].append(a-1)
    ln.append([a-1,b-1])

if k==1:
    print(n-2)
    exit()

from collections import deque
def get_v(node,dist):
    Q = deque()
    Q.append([node,0])
    visited=[-1]*n
    visited[node]=1
    while Q:
        now,cnt = Q.popleft()
        if cnt > dist:
            break
        for nxt in link[now]:
            if visited[nxt]!=-1:
                continue
            visited[nxt]=cnt+1
            Q.append([nxt,cnt+1])
    for i in range(n):
        if visited[i] == -1:
            ret = 0
        elif visited[i] <= dist:
            ret = 1
        else:
            ret = 0
        visited[i] = ret
    return visited
def borsm(l1,l2):
    sm=0
    for b1,b2 in zip(l1,l2):
        sm+=(b1 | b2)
    return sm
ans=float("inf")
if k%2==0:
    for i in range(n):
        ret = n - sum(get_v(i,k//2))
        ans=min(ret,ans)
else:
    for tmp in ln:
        n1,n2=tmp
        c1=get_v(n1,k//2)
        c2=get_v(n2,k//2)
        ret = n- borsm(c1,c2)
        ans=min(ret,ans)
print(ans)
### BUGGY CODE ###

S = input()
N = input()
N = int(N)
re = False
for i in range(N):
    que = input().split(" ")
    if que[0] == "1":
        if re:
            re = False
        else:
            re = True
    else:
        if re:
            if que[1] == "1":
                S += que[2]
            else:
                S = que[2]+S
        else:
            if que[1] == "1":
                S = que[2]+S
            else:
                S += que[2]
if re:
    S = S[::-1]
print(S)

### FIXED CODE ###

S = input()
N = input()
N = int(N)
re = False
foward = ""
back = ""

for i in range(N):
    que = input().split(" ")
    if que[0] == "1":
        if re:
            re = False
        else:
            re = True
    else:
        if re:
            if que[1] == "1":
                back += que[2]
            else:
                foward += que[2]
        else:
            if que[1] == "1":
                foward += que[2]
            else:
                back += que[2]
S = foward[::-1]+S+back
if re:
    print(S[::-1])
else:
    print(S)
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

a,b,n = map(int,input().split())
ans = 0

for i in range(1,min(b+1,n+1)):
    d = math.floor((a*i)/b)
    e = a*math.floor(i/b)
    if e>0:
        break
    ans = max(ans,d-e)
print(ans)

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

a,b,n = map(int,input().split())
ans = 0

if n < b-1:
    ans = math.floor((a*n)/b)
else:
    ans = math.floor((a*(b-1))/b)
print(ans)
### BUGGY CODE ###

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

Total = 0
for i in range(N):
    Synmmetry = True
    for a in range(N):
        for b in range(a, N):
            if S[a][(b + i) % N] != S[b][(a + i) % N]:
                Synmmetry = False
                break
        if not Synmmetry: break
    else: Total += 1
print(Total * N)

### FIXED CODE ###

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

Total = 0
for i in range(N):
    Synmmetry = True
    for a in range(N):
        for b in range(a, N):
            if S[a][(b + i) % N] != S[b][(a + i) % N]:
                Synmmetry = False
                break
        if not Synmmetry: break
    else: Total += 1
print(Total * N)
### BUGGY CODE ###

N, P = map(int, input().split())
ans = 1
def main(n, p):
  global ans
  for i in range(2, int(p**(2/n))):
    t = i**n
    if p % t == 0:
      ans *= i
      return main(n, p//t)
  return ans

print(main(N, P))

### FIXED CODE ###

N, P = map(int, input().split())
ans = 1
def main(n, p):
  if n == 1:
    return P
  global ans
  for i in range(2, int(p**(2/n))):
    t = i**n
    if p % t == 0:
      ans *= i
      return main(n, p//t)
  return ans

print(main(N, P))
### BUGGY CODE ###

#ABC116D-VariousSushi.py

import sys
import numpy as np
from operator import itemgetter

input = sys.stdin.readline

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = [[None] * N for _ in range(N)]
Score= 0
kind = [None] * K
kindnumber = 0

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters[i] = [INPUT2[0], INPUT2[1]]

Parameters = sorted(Parameters, key=itemgetter(1), reverse=True)

def SearchNew(List, kind, I):
    newkind = -1
    kindset = kind[:]
    oldkindnumber = len(set(kindset))
    newkindnumber = 0
    for i in range(len(List)-I):
        kindset.append(List[I+i][0])
        newkindnumber = len(set(kindset))
        if oldkindnumber != newkindnumber:
            newkind = I+i
            break
    return newkind

def SearchDouble(List, kind, J):
    result = -1
    testkind = kind[:]
    oldkindnumber = len(set(testkind))
    testkindPop = testkind.pop
    for i in range(J):
        testkindPop(J-1-i)
        newkindnumber = len(set(testkind))
        if oldkindnumber == newkindnumber:
            result = J-1-i
            break
        oldkindnumber = newkindnumber
    return result

for i in range(K):
    kind[i] = Parameters[i][0]
kindnumber = len(set(kind))
Score = np.sum(Parameters[:K], axis=0)[1] + kindnumber**2

Test1, Test2 = 0, Score

I, J = K, K

for t in range(N):
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, kind, I)
    j = SearchDouble(Parameters, kind, J)
    if i != -1 and j != -1:
        kindnumber += 1
        I, J = i, j
        kind[j] = Parameters[i][0]
        Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    else:
        break
    Test1 = Test2 - Parameters[i][1] + Parameters[j][1] + kindnumber * 2 - 1
    Test2 = Test1
    if Score <= Test2:
        Score = Test2

print(Score)


### FIXED CODE ###

#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

INPUT.sort(key = lambda x: -x[1])

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)
### BUGGY CODE ###

def main():
    H, W, D = list(map(int, input().split()))
    b = [None] * (H * W)
    for h in range(H):
        for w, a in enumerate(map(int, input().split())):
            b[a - 1] = (h, w)
    C = [0] * (H * W)
    for i in range(H * W - D):
        hi, wi = b[i]
        hn, wn = b[i + D]
        C[i] = abs(hi - hn) + abs(wi - wn)
    Q = int(input())
    r = 0
    cache = {}
    for _ in range(Q):
        l, r = map(int, input().split())
        if (l, r) not in cache:
            cache[(l, r)] = sum(C[l - 1:r - 1:D])
        print(cache[(l, r)])
        
main()


### FIXED CODE ###

def main():
    H, W, D = list(map(int, input().split()))
    b = [None] * (H * W)
    for h in range(H):
        for w, a in enumerate(map(int, input().split())):
            b[a - 1] = (h, w)
    C = [0] * (H * W)
    for i in range(H * W - D):
        hi, wi = b[i]
        hn, wn = b[i + D]
        C[i] = abs(hi - hn) + abs(wi - wn)
    E = [0] * (H * W)
    for i in reversed(range(H * W - D)):
            E[i] = E[i + D] + C[i]
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        print(E[l - 1] - E[r - 1])
        
main()
### BUGGY CODE ###

n=int(input())
a=[]

a.append(str(input()))

for i in range(n-1):
  flag = 1
  tmp = str(input())
  for j in range(len(a)):
    if a[j] == tmp:
      flag = 0
      break
  if flag == 1:
    a.append(tmp)

print(len(a))

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
  a.append(str(input()))

ans=1
a=sorted(a)
tmp=a[0]
for i in range(n-1):
  if a[i+1] != tmp:
    ans += 1
    tmp=a[i+1]

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

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(n)]

    N=0
    id=[[None]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            id[i][j]=N
            N+=1

    to_id=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        for j in range(n-2):
            u=to_id(i,A[i][j])
            v=to_id(i,A[i][j+1])
            E[u].append(v)

    # longest path problem
    dp=[None]*N
    visited=[0]*N

    def dfs(v):
        if(dp[v] is not None): return dp[v]
        visited[v]=1
        res=0
        for nv in E[v]:
            if((dp[nv] is None) and visited[nv]):
                print(-1)
                exit(0)
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print(max(dp)+1 if(flag) else -1)
resolve()
### BUGGY CODE ###

n = int(input())

p = [int(s) for s in input().split()]
flag = -1
m_ans = 0
for i in range(n):
    i_min = min(p[:i+1])
    if(i_min < p[i]):
        #print(p[j],p[i])
        m_ans += 1
    


print(n - m_ans)

### FIXED CODE ###

n = int(input())

p = [int(s) for s in input().split()]
flag = -1
m_ans = 1
p_z = p[0]
for i in range(1,n):
    p_z = min(p_z,p[i])
    if(p_z >= p[i]):
        #print(p[j],p[i])
        m_ans += 1
    
print(m_ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def main():
    N = int(input())
    C = []
    S = []
    F = []
    for _ in range(N-1):
        c,s,f = map(int,input().split())
        C.append(c)
        S.append(s)
        F.append(f)
    
    for i in range(N-1):
        t = 0
        for j in range(i,N-1):
            wait = 0
            if t <= S[j]:
                wait = S[j] - t
            else:
                x = S[j]
                while x < t:
                    x += F[j]
                wait = x - t
            t += wait + C[j]
        print(t)
    print(0)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
import math

def main():
    N = int(input())
    C = []
    S = []
    F = []
    for _ in range(N-1):
        c,s,f = map(int,input().split())
        C.append(c)
        S.append(s)
        F.append(f)
    
    for i in range(N-1):
        t = 0
        for j in range(i,N-1):
            k = max(0, math.ceil((t - S[j])/F[j]))
            t = S[j] + k*F[j] + C[j]
        print(t)
    print(0)

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



N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]

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

def dfs(u):
  visited = ["white"] * (N + 1)
  stack = [(u, -1, -1)]
  mcolor = -1

  while stack:
    u, p, c = stack.pop()
    visited[u] = "black"

    next = 1
    for v in edges[u]:
      if v != p and visited[v] != "black":
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        stack.append((v, u, next))
        next += 1
  
  return mcolor

print(dfs(1))

for edge in E:
  a, b = edge
  print(A[a][b])

### FIXED CODE ###


N = int(input())
edges = [[] for _ in range(N+1)]


for i in range(N-1):
  a, b = map(int, input().split())
  if i == 0:
    root = a
  edges[a].append((b, i))
  edges[b].append((a, i))

ans = [-1 for i in range(N-1)]
def dfs(u):
  flag = ["white"] * (N + 1)
  stack = [(u, -1, -1)]

  while stack:
    u, parent, color = stack.pop()
    flag[u] = "black"

    nextColor = 1
    for (next, index) in edges[u]:
      if next != parent and flag[next] != "black":
        if nextColor == color:
          nextColor += 1
        stack.append((next, u, nextColor))
        ans[index] = nextColor
        nextColor += 1

dfs(root)

print(max(ans))

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

from heapq import heappop,heappush
N,M = map(int,input().split())
T = [[] for i in range(N)]
for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)

INF = float("inf")
D = [INF]*N
A = [0]*N
Q = [[0,0,-1]]
while Q:
    d,v,p = heappop(Q)
    if d >= D[v]:continue
    A[v] = p
    D[v] = d
    d += 1
    for c in T[v]:
        heappush(Q,[d,c,v])
if INF in D:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(A[i]+1)

### FIXED CODE ###

from heapq import heappop,heappush
N,M = map(int,input().split())
T = [[] for i in range(N)]
for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)

INF = float("inf")
D = [INF]*N
A = [0]*N
Q = [[0,0,-1]]
while Q:
    d,v,p = heappop(Q)
    if d >= D[v]:continue
    A[v] = p
    D[v] = d
    d += 1
    for c in T[v]:
        if c == p:continue
        if d >= D[c]:continue
        heappush(Q,[d,c,v])
if INF in D:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(A[i]+1)
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
INF = 10 ** 12

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

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

vec_ = [[] for _ in range(N)]
for i in range(N) :
    queue = deque([(0, i)])
    while queue :
        step, q = queue.popleft()
        if step == 3 : 
            vec_[i].append(q)
            continue
            
        for j in vec[q] :
            queue.append((step + 1, j))
      
visited = [False] * N
visited[S] = True
queue = deque([(0, S)])
while queue :
    step, q = queue.popleft()
    if q == T : 
        break
    for i in vec_[q] :
        if not visited[i] :
            queue.append((step + 1, i))
            visited[i] = True

if visited[T] :
    print(step)
else :
    print(-1)
    

### FIXED CODE ###

from collections import deque

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

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

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

visited = [[False] * N for _ in range(3)]
visited[0][S] = True
queue = deque([(S, 0)])

while queue :
    q, cost = queue.popleft()
    p = (cost + 1) % 3
    for i in vec[q] :
        if p == 0 and i == T :
            print((cost + 1) // 3)
            exit()
        if not visited[p][i] :
            visited[p][i] = True
            queue.append((i, cost + 1))

print(-1)
### BUGGY CODE ###

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

pp_ex = list(map(lambda p: (p * (p + 1) / 2) / p, pp))

max_ex = 0
for i in range(n - k + 1):
    ex = 0
    for j in range(k):
        ex += pp_ex[i + j]
    if max_ex < ex:
        max_ex = ex

print(max_ex)


### FIXED CODE ###

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

pp_ex = list(map(lambda p: (p + 1) / 2, pp))

max_ex = 0
for i in range(k):
    max_ex += pp_ex[i]
bef_ex = max_ex
for i in range(1, n - k + 1):
    ex = bef_ex - pp_ex[i - 1] + pp_ex[i + k - 1]
    bef_ex = ex
    if max_ex < ex:
        max_ex = ex

print(max_ex)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]+[float("inf")]*(N-1)
for i in range(N):
    for k in range(1,K+1):
        if i+k > N-1:
            break
        dp[i+k] = min(dp[i+k],dp[i]+abs(h[i+k]-h[i]))
print(dp[N-1])


### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]+[float("inf")]*(N-1)
for i in range(N):
    for k in range(1,K+1):
        if i+k > N-1:
            break
        dp[i+k] = min(dp[i+k],dp[i]+abs(h[i+k]-h[i]))
print(dp[N-1])