CodeEff/ECCO huggingface dataset:
# Original solution
int1 = lambda x: int(x) - 1
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

start_point = set(range(N))
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = list(map(int1, input().split()))
    start_point = start_point - {y}
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

for i in range(N):
    dp(i)

print((max(dp_memo)))

# Optimized solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

int1 = lambda x: int(x) - 1

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

to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = list(map(int1, input().split()))
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

for i in range(N):
    dp(i)

print((max(dp_memo)))
# Original solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

int1 = lambda x: int(x) - 1

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

to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = list(map(int1, input().split()))
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

for i in range(N):
    dp(i)

print((max(dp_memo)))

# Optimized solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

int1 = lambda x: int(x) - 1

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

not_start_point = set()
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = list(map(int1, input().split()))
    not_start_point.add(y)
    to_point[x].append(y)

start_point = set(range(N)) - not_start_point

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

ans = 0
for s in start_point:
    ans = max(ans, dp(s))

print(ans)
# Original solution
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 7)


def input():
    return sys.stdin.readline().strip()


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    res = 0
    for nv in g[v]:
        res = max(res, dfs(nv) + 1)
    dp[v] = res
    return res


n, m = list(map(int, input().split()))
g = {i: set() for i in range(n)}
for _ in range(m):
    x, y = list(map(int, input().split()))
    g[x - 1].add(y - 1)

dp = defaultdict(lambda: -1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
print((max(dp.values())))


# Optimized solution
import sys
sys.setrecursionlimit(10 ** 7)


def input():
    return sys.stdin.readline().strip()


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    res = 0
    for nv in g[v]:
        res = max(res, dfs(nv) + 1)
    dp[v] = res
    return res


n, m = list(map(int, input().split()))
g = [[] for i in range(n)]
for _ in range(m):
    x, y = list(map(int, input().split()))
    g[x - 1].append(y - 1)

dp = [-1] * n
for v in range(n):
    dp[v] = max(dp[v], dfs(v))
print((max(dp)))
# Original solution
import sys
input = sys.stdin.readline
n,m = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
path = [0 for i in range(n+1)]
for a,b in ab:
  graph[b].append(a)
  path[a] = -1
stack = []
for i in range(1,n+1):
  if path[i] == 0:
    stack.append(i)
    while stack:
      x = stack.pop()
      for y in graph[x]:
        if path[x]+1 > path[y]:
          stack.append(y)
          path[y] = path[x]+1
print((max(path)))

# Optimized solution
import sys
input = sys.stdin.readline
n,m = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
path = [0 for i in range(n+1)]
con = [0 for i in range(n+1)]
for a,b in ab:
  graph[b].append(a)
  path[a] = -1
  con[a] += 1
stack = []
for i in range(1,n+1):
  if path[i] == 0:
    stack.append(i)
    while stack:
      x = stack.pop()
      for y in graph[x]:
        path[y] = max(path[y],path[x]+1)
        con[y] -= 1
        if con[y] == 0:
          stack.append(y)
print((max(path)))
# Original solution
from collections import deque

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

g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]

for _ in range(m):
    x, y = list(map(int, input().split()))
    g[x-1].append(y-1)
    indeg[y-1] += 1

q = deque([])
dp = [-1 for _ in range(n)]

for i in range(n):
    if indeg[i] == 0:
        q.append(i)
        dp[i] = 0

while q:
    v = q.popleft()
    for w in g[v]:
        if dp[w] < dp[v]+1:
            dp[w] = dp[v]+1
            q.append(w)

print((max(dp)))



# Optimized solution
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]

for _ in range(m):
    x, y = list(map(int, input().split()))
    g[x-1].append(y-1)
    indeg[y-1] += 1

dp = [-1 for _ in range(n)]


def LP(v):
    if dp[v] != -1:
        return dp[v]
    ans = 0
    for w in g[v]:
        ans = max(ans, LP(w)+1)
    dp[v] = ans
    return dp[v]


for i in range(n):
    LP(i)

print((max(dp)))
# Original solution
import sys
sys.setrecursionlimit(10**9)


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

for _ in range(M):
    x, y = list(map(int, input().split()))
    to[x - 1].append(y - 1)


count = 0
def dfs(v, seen, temp=0):
    global count
    seen[v] = 1
    if to[v]:
        for nv in to[v]:
            dfs(nv, seen, temp + 1)
    else:
        count = max(count, temp)


def main():
    ans = 0
    seen = [0] * N
    for i in range(N):
        if not seen[i]:
            dfs(i, seen)
            ans = max(ans, count)
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
import sys
sys.setrecursionlimit(10**9)


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

for _ in range(M):
    x, y = list(map(int, input().split()))
    to[x - 1].append(y - 1)

# dp[i] : iを始点とする最長経路
dp = [0] * N
seen = [0] * N

def dfs(v):
    if seen[v]:
        return dp[v]
    seen[v] = 1
    res = 0
    for nv in to[v]:
        res = max(res, dfs(nv) + 1)
    dp[v] = res
    return res


def main():
    ans = 0
    for i in range(N):
        ans = max(ans, dfs(i))
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
import sys
sys.setrecursionlimit(10**6)
def dfs(v):
    seen[v]=1
    for nv in G[v]:
        if seen[nv]:
            continue
        dfs(nv)
    topo.append(v)

N,M=list(map(int,input().split()))
G=[[] for i in range(N)]
for i in range(M):
    x,y=[int(x)-1 for x in input().split()]
    G[x].append(y)
seen=[0]*N
topo=[]
for i in range(N):
    if not seen[i]:
        dfs(i)
dp=[0]*N
for v in reversed(topo):
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print((max(dp)))

# Optimized solution
import sys
sys.setrecursionlimit(10**6)
def dfs(v):
    if(dp[v]==-1):
        dp[v]=0
        for nv in G[v]:
            dp[v]=max(dp[v],dfs(nv)+1)
    return dp[v]
N,M=list(map(int,input().split()))
G=[[] for i in range(N)]
for i in range(M):
    x,y=[int(x)-1 for x in input().split()]
    G[x].append(y)
dp=[-1]*N
res=-1
for v in range(N):
    res=max(res,dfs(v))
print(res)
# Original solution
n, m = list(map(int, input().split()))
path = {}
ans = []

for i in range(m):
    x, y = list(map(int, input().split()))
    if not x in list(path.keys()):
        path[x] = []
    path[x].append(y)
    
def get_next_node(current):
    next_node = []
    for c in current:
        if not c in list(path.keys()):
            continue
        next_node += path[c]
    return next_node
    
for j in range(1, n+1):
    count = 0
    if not j in list(path.keys()):
        continue
    next_node = path[j]
    while len(next_node) != 0:
        next_node = get_next_node(next_node)
        count += 1
    ans.append(count)

print((max(ans)))

# Optimized solution
n, m = list(map(int, input().split()))
path = {}
ans = []

for i in range(m):
    x, y = list(map(int, input().split()))
    if not x in list(path.keys()):
        path[x] = []
    path[x].append(y)
    
def get_next_node(current):
    next_node = []
    for c in current:
        if not c in list(path.keys()):
            continue
        next_node += path[c]
    return list(set(next_node))
    
for j in range(1, n+1):
    count = 0
    if not j in list(path.keys()):
        continue
    next_node = path[j]
    while len(next_node) != 0:
        next_node = get_next_node(next_node)
        count += 1
    ans.append(count)

print((max(ans)))
# Original solution
import sys
sys.setrecursionlimit(10**6)
edges, vertices = list(map(int, input().split()))
dp = [None for _ in range(edges)]

nodes = [[] for _ in range(edges)]

for i in range(vertices):
    start, end = list(map(int, input().split()))
    nodes[end -1].append(start-1)

def find(arr):
    if not len(arr):
        return 0
    for x in arr:
        if dp[x] is None:
            dp[x] = find(nodes[x])
    return 1 + max(dp[x] for x in arr)

for i in range(edges):
    dp[i] = find(nodes[i])

print((max(dp)))


# Optimized solution
import sys
sys.setrecursionlimit(10**6)
edges, vertices = list(map(int, input().split()))
dp = [None for _ in range(edges)]

nodes = [[] for _ in range(edges)]

for i in range(vertices):
    start, end = list(map(int, input().split()))
    nodes[end -1].append(start-1)

for i in range(edges):
    if not len(nodes[i]):
        dp[i] = 0
def find(arr):
    if not len(arr):
        return 0
    for x in arr:
        if dp[x] is None:
            dp[x] = find(nodes[x])
    return 1 + max(dp[x] for x in arr)

for i in range(edges):
    dp[i] = find(nodes[i])

print((max(dp)))
# Original solution
from sys import stdin
import math
import fractions
from collections import deque
import sys

# 再起の上限を変更
sys.setrecursionlimit(100000)

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.insert(0, i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    xv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]

    # トポロジカルソートで頂点iより後ろのパスの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for x, v in xv:
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = []

    is_visited = [False] * (N+1)

    tsort()

    # 今回は逆順に使うのでリバースする
    # 汎用性のため、dfsでは先頭に追加するようにしている
    tsort_res = tsort_res[::-1]

    for x in tsort_res:
        for v in nextl[x]:
            dp[x] = max(dp[x], dp[v] + 1)


    # for DEBUG
    #print(dp)
    print((max(dp)))

# Optimized solution
from sys import stdin
import math
import fractions
from collections import deque
import sys

# 再起の上限を変更
sys.setrecursionlimit(100000)

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.appendleft(i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]

    # トポロジカルソートで頂点iより後ろのパスの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for _ in range(M):
        x, v = list(map(int, stdin.readline().rstrip().split()))
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = deque([])

    is_visited = [False] * (N+1)

    tsort()

    # 今回は逆順に使うのでリバースする
    # 汎用性のため、dfsでは先頭に追加するようにしている
    tsort_res = list(tsort_res)[::-1]

    for x in tsort_res:
        for v in nextl[x]:
            dp[x] = max(dp[x], dp[v] + 1)


    # for DEBUG
    #print(dp)
    print((max(dp)))
# Original solution
from sys import stdin
import math
import fractions
from collections import deque
import sys

# 再起の上限を変更
sys.setrecursionlimit(100000)

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.appendleft(i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]

    # トポロジカルソートで頂点iより後ろのパスの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for _ in range(M):
        x, v = list(map(int, stdin.readline().rstrip().split()))
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = deque([])

    is_visited = [False] * (N+1)

    tsort()

    # 今回は逆順に使うのでリバースする
    # 汎用性のため、dfsでは先頭に追加するようにしている
    tsort_res = list(tsort_res)[::-1]

    for x in tsort_res:
        for v in nextl[x]:
            dp[x] = max(dp[x], dp[v] + 1)


    # for DEBUG
    #print(dp)
    print((max(dp)))

# Optimized solution
from sys import stdin
import math
import fractions
from collections import deque
import sys

# 再起の上限を変更
sys.setrecursionlimit(100000)

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.appendleft(i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]

    # トポロジカルソートで頂点iより後ろのパスの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for _ in range(M):
        x, v = list(map(int, stdin.readline().rstrip().split()))
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = deque([])

    is_visited = [False] * (N+1)

    # トポロジカルソートの実行
    tsort()

    # 今回は逆順に使うのでリバースする
    # つまり、トポロジカルオーダーの最後の番号に該当する頂点から処理を行う
    # 汎用性のため、dfsでは先頭に追加するようにしている
    #tsort_res = list(tsort_res)[::-1]

    """
    for x in tsort_res:
        for v in nextl[x]:
            dp[x] = max(dp[x], dp[v] + 1)
    """
    for x in tsort_res:
        for v in nextl[x]:
            dp[v] = max(dp[v], dp[x] + 1)


    # for DEBUG
    #print(dp)
    print((max(dp)))
# Original solution
import heapq
INF=float('inf')

n,m=list(map(int,input().split()))
adj=[[] for _ in range(n)]
for _ in range(m):
  x,y=list(map(int,input().split()))
  x-=1
  y-=1
  adj[x].append(y)

ans=-INF
for i in range(n):
  dist=[-INF for _ in range(n)]
  Q=[(0,i)]
  dist[i]=0
  heapq.heapify(Q)
  while Q:
    d,v=heapq.heappop(Q)
    for nv in adj[v]:
      if dist[nv]<dist[v]+1:
        dist[nv]=dist[v]+1
        heapq.heappush(Q,(dist[nv],nv))
  ans=max(ans,max(dist))
  
print(ans)

# Optimized solution
import sys

sys.setrecursionlimit(10**9)
INF=float('inf')

n,m=list(map(int,input().split()))
adj=[[] for _ in range(n+1)]
for _ in range(m):
  x,y=list(map(int,input().split()))
  adj[x].append(y)
  
dp=[-1 for _ in range(n+1)]

def f(k):
  if dp[k]!=-1:
    return dp[k]
  
  dp[k]=0
  if adj[k]:
    for v in adj[k]:
      dp[k]=max(dp[k],f(v)+1)
  return dp[k]

ans=-INF  
for i in range(1,n+1):
  ans=max(ans,f(i))

print(ans)
# Original solution
import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
matrix = [[0]*N for i in range(N)]
for _ in range(M):
    x,y = list(map(int,input().split()))
    x -= 1; y -= 1
    matrix[x][y] = 1

dp = [-1]*N

def rec(nodes):
    if dp[nodes] != -1:
        return dp[nodes]
    res = 0
    for ne,bit in enumerate(matrix[nodes]):
        if bit == 0:continue
        option = rec(ne)+1
        if res < option:
            res = option
    dp[nodes] = res
    return dp[nodes]

ans = 0
for i in range(N):
    res = rec(i)
    if ans < res:
        ans = res
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N,M = list(map(int,input().split()))
ad = [[] for i in range(N)]
for _ in range(M):
    x,y = list(map(int,input().split()))
    x -= 1; y -= 1
    ad[x].append(y)

dp = [-1]*N

def rec(nodes):
    if dp[nodes] != -1:
        return dp[nodes]
    res = 0
    for ne in ad[nodes]:
        option = rec(ne)+1
        if res < option:
            res = option
    dp[nodes] = res
    return dp[nodes]

ans = 0
for i in range(N):
    res = rec(i)
    if ans < res:
        ans = res
print(ans)
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N,M = list(map(int,input().split()))
ad = [[] for i in range(N)]
for _ in range(M):
    x,y = list(map(int,input().split()))
    x -= 1; y -= 1
    ad[x].append(y)

dp = [-1]*N

def rec(nodes):
    if dp[nodes] != -1:
        return dp[nodes]
    res = 0
    for ne in ad[nodes]:
        option = rec(ne)+1
        if res < option:
            res = option
    dp[nodes] = res
    return dp[nodes]

ans = 0
for i in range(N):
    res = rec(i)
    if ans < res:
        ans = res
print(ans)

# Optimized solution
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    N,M = list(map(int,input().split()))
    ad = [[] for i in range(N)]
    for _ in range(M):
        x,y = list(map(int,input().split()))
        x -= 1; y -= 1
        ad[x].append(y)

    dp = [-1]*N

    def rec(nodes):
        if dp[nodes] != -1:
            return dp[nodes]
        res = 0
        for ne in ad[nodes]:
            option = rec(ne)+1
            if res < option:
                res = option
        dp[nodes] = res
        return dp[nodes]

    ans = 0
    for i in range(N):
        res = rec(i)
        if ans < res:
            ans = res
    print(ans)
    
main()
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M = list(map(int, readline().split()))
outdeg = {i: [] for i in range(N)}
for _ in range(M):
    a, b = list(map(int, readline().split()))
    a -= 1
    b -= 1
    outdeg[a].append(b)

dp = [-1] * (N)


def rec(s):
    if dp[s] != -1:
        return dp[s]

    res = 0
    for t in outdeg[s]:
        res = max(res, rec(t)+1)
    dp[s] = res
    return res


ans = 0
for s in range(N):
    ans = max(ans, rec(s))
print(ans)


# Optimized solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


N, M = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for _ in range(M):
    s, t = list(map(int, input().split()))
    s -= 1
    t -= 1
    edge[s].append(t)

dp = [-1]*N

def dfs(s):
    if dp[s] != -1:
        return dp[s]
    if len(edge[s]) == 0:
        dp[s] = 0
        return 0
    res = 0
    for t in edge[s]:
        res = max(res, dfs(t)+1)
    dp[s] = res
    return res

for i in range(N):
    dfs(i)
print((max(dp)))
# Original solution
import heapq
def sol(inp=input):
    n,m=list(map(int,inp().split()))
    G={i+1:set() for i in range(n)}
    for _ in range(m):
        i,j=list(map(int,inp().split()))
        G[i].add(j)
    s,t=list(map(int,inp().split()))
    cache_kenken={}
    def kenken(v):
        if v not in cache_kenken:
            cache_kenken[v]=set(v2 for v1 in G[v] for v2 in G[v1])
        return cache_kenken[v]
    def kenkenpa(v):
        return set(v3 for v2 in kenken(v) for v3 in G[v2])
    visited={s}
    revisited=set()
    v_steps=[]
    visited_pa={s}
    que=[]
    heapq.heappush(que,(0,s))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in kenkenpa(u):
            if v not in visited:
                visited.add(v)
                v_steps.append((step+1,v))
                heapq.heappush(que,(step+1,v))
            if v==t:
                return step+1
            if v not in visited:
                visited.add(v)
    return -1
print((sol()))

# Optimized solution
import heapq
def sol(inp=input):
    s=3
    n,m=list(map(int,inp().split()))
    G={(i+1,j):set() for i in range(n) for j in range(s)}
    for _ in range(m):
        u,v=list(map(int,inp().split()))
        for i in range(s):
            G[(u,i)].add((v,(i+1)%s))
    s,t=list(map(int,inp().split()))
    visited={(s,0)}
    que=[]
    heapq.heappush(que,(0,(s,0)))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in G[u]:
            if v not in visited:
                visited.add(v)
                heapq.heappush(que,(step+1,v))
            if v==(t,0):
                return (step+1)//3
    return -1
print((sol()))
# Original solution
import copy
n,m=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(m)]
s,t=list(map(int,input().split()))

connection=[[] for i in range(3*n)]
for i in range(m):
  connection[l[i][0]-1].append(l[i][1]-1+n)
  connection[l[i][0]-1+n].append(l[i][1]-1+2*n)
  connection[l[i][0]-1+2*n].append(l[i][1]-1)
distance=[-1 for i in range(3*n)]
distance[s-1]=0
L=[s-1]
L2=[]
L3=[]
ct=1
while len(L2)!=3*n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      if distance[connection[L[j]][k]]==-1:
        distance[connection[L[j]][k]]=ct
        L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
  ct+=1
if distance[t-1]==-1:
  print((-1))
else:
  x=distance[t-1]-distance[s-1]
  if x%3==0:
    print((x//3))
  else:
    print((-1))

# Optimized solution
n,m=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(m)]
s,t=list(map(int,input().split()))

connection=[[] for i in range(3*n)]
for i in range(m):
  connection[l[i][0]-1].append(l[i][1]-1+n)
  connection[l[i][0]-1+n].append(l[i][1]-1+2*n)
  connection[l[i][0]-1+2*n].append(l[i][1]-1)

def bfs(v):
  distance=[-1]*(3*n)
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*(3*n)
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=3*n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

if bfs(s-1)[t-1]==-1 or bfs(s-1)[t-1]%3!=0:
  print((-1))
else:
  print((bfs(s-1)[t-1]//3))