Harryxun/stf_run huggingface dataset:
N = int(input())
d = [0]*N
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    d[a-1]+=1
    d[b-1]+=1
    G[a-1].append((i, b-1))
    G[b-1].append((i, a-1))
K = max(d)
ans = [0]*(N-1)
def dfs(v, p, c):
    if G[v] == [p]:
        return 
    nc = 1
    for i, nv in G[v]:
        if nv == p:
            continue
        if nc == c:
            nc+=1
        ans[i] = nc
        dfs(nv, v, nc)
        nc+=1
    return
dfs(0, -1, -1)
print(K)
print(*ans, sep = '\n')
        




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
N = int(input())
d = [0]*N
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    d[a-1]+=1
    d[b-1]+=1
    G[a-1].append((i, b-1))
    G[b-1].append((i, a-1))
K = max(d)
ans = [0]*(N-1)
def dfs(v, p, c):
    if G[v] == [p]:
        return 
    nc = 1
    for i, nv in G[v]:
        if nv == p:
            continue
        if nc == c:
            nc+=1
        ans[i] = nc
        dfs(nv, v, nc)
        nc+=1
    return
dfs(0, -1, -1)
print(K)
print(*ans, sep = '\n')
N, K = map(int, input().split())
S = input()

H0 = 0
N_LR = 0
N_RL = 0

if S[0] == 'R' and S[1] == 'R':
    H0 += 1
if S[0] == 'R' and S[1] == 'L':
    N_RL += 1
if S[0] == 'L' and S[1] == 'R':
    N_LR += 1

if S[N-1] == 'L' and S[N-2] == 'L':
    H0 += 1

for i in range(1, N-1):
    if S[i] == 'L' and S[i-1] == 'L' or S[i] == 'R' and S[i+1] == 'R':
        H0 += 1
    if S[i] == 'R' and S[i+1] == 'L':
        N_RL += 1
    if S[i] == 'L' and S[i+1] == 'R':
        N_LR += 1

M = min(N_RL, N_LR, K)
H1 = H0 + 2 * M
K -= M
N_RL -= M
N_LR -= M

result = H1 + min(K, max(N_RL, N_LR))
print(result)


### FIXED CODE ###

N, K = map(int, input().split())
S = input()

if N == 1:
    print(0)
else:
    H = 0
    N_LR = 0
    N_RL = 0

    if S[0] == 'R' and S[1] == 'R':
        H += 1
    if S[0] == 'R' and S[1] == 'L':
        N_RL += 1
    if S[0] == 'L' and S[1] == 'R':
        N_LR += 1

    if S[N-1] == 'L' and S[N-2] == 'L':
        H += 1

    for i in range(1, N-1):
        if S[i] == 'L' and S[i-1] == 'L' or S[i] == 'R' and S[i+1] == 'R':
            H += 1
        if S[i] == 'R' and S[i+1] == 'L':
            N_RL += 1
        if S[i] == 'L' and S[i+1] == 'R':
            N_LR += 1

    M = min(N_RL, N_LR, K)
    H += 2 * M
    K -= M
    N_RL -= M
    N_LR -= M

    s0 = S[0]
    while K > 0 and (s0 == 'R' and N_RL > 0 or s0 == 'L' and N_LR > 0):
        if s0 == 'R' and N_RL > 0:
            H += 1
            s0 = 'L'
            N_RL -= 1
            K -=1
        elif s0 == 'L' and N_LR > 0:
            H += 1
            s0 = 'R'
            N_LR -= 1
            K -=1

    sN = S[N-1]
    while K > 0 and (sN == 'R' and N_LR > 0 or sN == 'L' and N_RL > 0):
        if sN == 'R' and N_LR > 0:
            H += 1
            sN = 'L'
            N_LR -= 1
            K -=1
        elif sN == 'L' and N_RL > 0:
            H += 1
            sN = 'R'
            N_RL -= 1
            K -=1

    print(H)
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = [0 for _ in range(n)]
f[0] = 1

v = [1]
s = 0
idx = 0
loop = 0
last = 1
for i in range(k):
    vi = a[last - 1]
    if not f[vi - 1]:
        f[vi - 1] = 1
        last = vi
        s += 1
        v.append(vi)
    else:
        s += 1
        idx = v.index(vi)
        loop = s - idx
        break
remain = k - s
print(v[idx:][remain % loop])

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
f = [0 for _ in range(n)]
f[0] = 1

v = [1]
s = 0
idx = 0
loop = 0
last = 1
for i in range(k):
    vi = a[last - 1]
    if not f[vi - 1]:
        f[vi - 1] = 1
        last = vi
        s += 1
        v.append(vi)
    else:
        s += 1
        idx = v.index(vi)
        loop = s - idx
        break
else:
    print(vi)
    exit()
remain = k - s
print(v[idx:][remain % loop])
class BIT:
  def __init__(self,n):
    self.N = n
    self.data = [0]*(N+1)
  def bit_add(self,i,a):
    j = i+1
    while j<=N:
      self.data[j] += a
      j += j&-j
  def bit_sum(self,i):
    m = 0
    j = i+1
    while j>0:
      m += self.data[j]
      j -= j&-j
    return m
  def bit_search(self,x):
    i = 0
    m = 0
    j = 1<<(self.N.bit_length()-1)
    while j:
      if i+j<=N and self.data[i+j]+m<=x:
        i += j
        m += self.data[i]
      j >>= 1
    return i
N, *A = map(int, open('0').read().split())
bit = BIT(N)
ntoi = [0]*(N+1)
ans = 0
for i, a in enumerate(A):
  ntoi[a] = i
for i in range(1,N+1):
  j = ntoi[i]
  L = bit.bit_sum(j)
  R = N-L-1
  if L!=0:
    a = bit.bit_search(L-1)
  else:
    a = -1
  if R!=0:
    b = bit.bit_search(L)
  else:
    b = N
  ans += (j-a)*(b-j)*i
  bit.bit_add(j,1)
print(ans)

### FIXED CODE ###

N = int(input())
p = [None]+[int(c) for c in input().split()]
p_to_i = [None]*(N+1)
for i, x in enumerate(p[1:],1):
  p_to_i[x] = i

tree = [0]*(N+1)

def BIT_add(i):
  while i<=N:
    tree[i] += 1
    i += i&(-i)
    
def BIT_sum(i):
  s = 0
  while 0<i:
    s += tree[i]
    i -= i&(-i)
  return s

def BIT_search(c):
  s = 0
  step = 1<<(N.bit_length()-1)
  i = 0
  while step:
    if i+step<=N and s+tree[i+step]<c:
      i += step
      s += tree[i]
    step >>= 1
  return i+1

ans = 0
for i in range(1,N+1):
  c = p_to_i[i]
  L = BIT_sum(c)
  R = i-1-L
  BIT_add(c)
  a = BIT_search(L) if L>0 else 0
  b = BIT_search(L+2) if R>0 else N+1
  m = (c-a)*(b-c)
  ans += m*i
#  print(i, ans, a, b, c, L, R)
print(ans)
# coding: utf-8
import sys
sys.setrecursionlimit(100)

def solve(a,begin,end,queue):
  if begin>=end:
    return
  maxx = sorted(list(map(abs,a[begin:end+1])),reverse=True)[0]
  if maxx in a:
    m = a.index(maxx)
  else:
    m = a.index(-1*maxx)
    maxx = -1*maxx
  if maxx==0:
    return []
  if maxx>0:
    solve(a,begin,m-1,queue)
    for i in range(max(0,m-1),end):
      if a[i+1]>=a[i]:
        continue
      else:
        a[i+1]+=a[i]
        queue.append((i,i+1))
        if a[i+1]<a[i]:
          a[i+1]+=a[i]
          queue.append((i,i+1))
    return queue
  if maxx<0:
    solve(a,m+1,end,queue)
    for i in reversed(range(begin,min(len(a)-1,m+1))):
      if a[i]<=a[i+1]:
        continue
      else:
        a[i]+= a[i+1]
        queue.append((i+1,i))
        if a[i]>a[i+1]:
          a[i]+=a[i+1]
          queue.append((i+1,i))
    return queue

if __name__ == '__main__':
  n = int(input())
  a = list(map(int,input().split()))
  queue = solve(a,0,len(a)-1,[])
  print(len(queue))
  for i in range(len(queue)):
    print(queue[i][0]+1,queue[i][1]+1)


### FIXED CODE ###

# coding: utf-8

def solve(a,begin,end,queue):
  if begin>=end:
    return
  maxx = sorted(list(map(abs,a[begin:end+1])),reverse=True)[0]
  if maxx in a[begin:end+1]:
    m = a[begin:end+1].index(maxx)+begin
  else:
    m = a[begin:end+1].index(-1*maxx)+begin
    maxx = -1*maxx
  if maxx==0:
    return []
  if maxx>0:
    solve(a,begin,m-1,queue)
    for i in range(max(0,m-1),end):
      if a[i+1]>=a[i]:
        continue
      else:
        a[i+1]+=a[i]
        queue.append((i,i+1))
        if a[i+1]<a[i]:
          a[i+1]+=a[i]
          queue.append((i,i+1))
    return queue
  if maxx<0:
    solve(a,m+1,end,queue)
    for i in reversed(range(begin,min(len(a)-1,m+1))):
      if a[i]<=a[i+1]:
        continue
      else:
        a[i]+= a[i+1]
        queue.append((i+1,i))
        if a[i]>a[i+1]:
          a[i]+=a[i+1]
          queue.append((i+1,i))
    return queue

if __name__ == '__main__':
  n = int(input())
  a = list(map(int,input().split()))
  queue = solve(a,0,len(a)-1,[])
  print(len(queue))
  for i in range(len(queue)):
    print(queue[i][0]+1,queue[i][1]+1)
listA = [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]
C = input()
for i in range(24):
  if C == listA[i]:
    print(listA[i+1])

### FIXED CODE ###

listA = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
C = input()
for i in range(25):
  if C == listA[i]:
    print(listA[i+1])
import sys
from collections import Counter
from math import ceil
def input():
    return sys.stdin.readline()[:-1]
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def main():
    N = int(input())
    P = []
    for _ in range(N):
        P.append(list(map(int,input().split())))
    K = []
    for k in range(N-1):
        for l in range(k+1,N):
            a, b, c, d = P[k][0], P[k][1], P[l][0], P[l][1]
            if [a,b] != [c,d]:
                e = c-a
                f = d-b
                while gcd(e,f) != 1:
                    t = gcd(e,f)
                    e //= t
                    f //= t
                K.append((e,f))
    C = Counter(K).most_common()
    print(max(1,N-C[0][1]))

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
N = int(input())
L = sorted([list(map(int,input().split())) for k in range(N)])
D = []
if N == 1:
    print(1)
    exit(0)
for k in range(N-1):
    for l in range(k+1,N):
        D.append((L[k][0]-L[l][0],L[k][1]-L[l][1]))

E = Counter(D).most_common()[0]
x, y = E[0][0], E[0][1]
used = []
ans = N
for k in range(N-1):
    for l in range(k+1,N):
        if L[k][0]-L[l][0] == x and L[k][1]-L[l][1] == y:
            if L[k] not in used and L[l] not in used:
                used.append(L[k])
                used.append(L[l])
                ans -= 1
            elif L[k] in used and L[l] not in used:
                used.append(L[l])
                ans -= 1
            elif L[k] not in used and L[l] in used:
                used.append(L[k])
                ans -= 1
            else:
                pass
print(ans)
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])
dp=[[[]] for j in range(w)] for k in range(h)]
dp[0][0].append(d[0][0])
for i in range(h):
    for j in range(w):
        for x in dp[i][j]:
            if i+1<h:
                dp[i+1][j].append(dis+d[i+1][j])
                dp[i+1][j].append(abs(dis-d[i+1][j]))
            if j+1<w:
                dp[i][j+1].append(dis+d[i][j+1])
                dp[i][j+1].append(abs(dis-d[i][j+1]))
m=10000000
for dis in dp[-1][-1]:
    m=min(m,dis)
print(m)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
maxd=1
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])
        maxd=max(maxd,d[i][j])
dp=[[0 for j in range(w)] for k in range(h)]
c=20000
dp[0][0] |= 1 << c+d[0][0]
for i in range(h):
    for j in range(w):
        if i+1<h:
            dp[i+1][j] |= dp[i][j] << d[i+1][j]
            dp[i+1][j] |= dp[i][j] >> d[i+1][j]
        if j+1<w:
            dp[i][j+1] |= dp[i][j] << d[i][j+1]
            dp[i][j+1] |= dp[i][j] >> d[i][j+1]
m=1000000
cnt = 0
for x in bin(dp[h-1][w-1])[2:][::-1]:
    if x=='1':
        m=min(m,abs(cnt-c))
    cnt+=1
print(m)
N = int(input())

i = 1
for i in range(1,10):
  if 2 ** i <= N:
    ans = 2*i

print(ans)

### FIXED CODE ###

n = int(input())

ans = 1
for i in range(1,10):
    if 2 ** i <= n:
        ans = 2**i

print(ans)
H,W,K=map(int, input().split())
C=[list(input().split())for _ in range(H)]

#H,Wが小さいことが肝
#つまり全通り試してみる

#itertoolのうちpermutationが順列、combinationが組み合わせ
#productが直積

ans=0
import itertools
tf=("Yes", "No")
for l in itertools.product(tf, repeat=(H+W)):
  L=list(l)
black=0
for i in range(2**(H+W)):
  for j in range(H):
    for k in range(W):
      if l[i][j]=="No"and l[i][H+k]=="No"and C[j][k]=="#":
        black+=1
  if black==K:
    ans+=1
    black=0
print(ans)


### FIXED CODE ###

H,W,K=map(int, input().split())
C=list(input()for _ in range(H))
ans=0
import itertools
tf=("Yes", "No")
l=list(itertools.product(tf, repeat=(H+W)))
black=0
for i in range(2**(H+W)):
  for j in range(H):
    for k in range(W):
      if l[i][j]=="No"and l[i][H+k]=="No"and C[j][k]=="#":
        black+=1
  if black==K:
    ans+=1
  black=0
print(ans)
r,g,b,n=map(int, input().split())

r_max=n//r
g_max=n//g

sum=0

for i in range((n//r)+1):
    for j in range((n-(i*r)//g)+1):
        if (n-(i*r)-(j*g))%b==0 and (n-(i*r)-(j*g))//b>=0:
            sum=sum+1
        #    print(i*r,j*g,(n-(i*r)-(j*g))%b)

print(sum)


### FIXED CODE ###

n,k=map(int, input().split())

print(n-k+1)
N, M, K = map(int, (input().split()))
a_timelist = int(input().split())
b_timelist = int(input().split())
counta = len(a_timelist)
countb = len(b_timelist)
time = 0
a, b = [0], [0]
for i in range(N):
  a.append(a[i] + a_timelist[i])
for i in range(M):
  b.append(b[i] + b_timelist[i])
ans, j = 0, M
for i in range(N+1):
  if a[i] > K:
    break
  while b[i] > K -a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)
N, M, K = int(input().split())
a_timelist = int(input().split())
b_timelist = int(input().split())
counta = len(a_timelist)
countb = len(b_timelist)
time = 0
a, b = [0], [0]
for i in range(N):
  a.append(a[i] + a_timelist[i])
for i in range(M):
  b.append(b[i] + b_timelist[i])
ans, j = 0, M
for i in range(N+1):
  if a[i] > K:
    break
  while b[i] > K -a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)
n=int(input())
s=list(map(int,list(input())))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
def f(lrc):
  l1,r1,c1,x1=lrc[0]
  for l2,r2,c2,x2 in lrc[1:]:
    l1,r1=max(max(l1,l2)-min(r1,r2),0),r1+r2
    if r1%2!=l1%2:l1+=1
    c1+=c2
    x1+=x2
  return [l1,r1,c1,x1]
def dfs(root,node):
  lrcx=[]
  for mode in edge[node]:
    if root!=mode:
      lrcx.append(dfs(node,mode))
  if len(lrcx)==0:
    return [s[node]]*4
  l,r,c,x=f(lrcx)
  c+=s[node]
  return [l+c,r+c,c,x+c]
anss=[]
for i in range(n):
  l,r,c,x=dfs(-1,i)
  if l==c:
    anss.append(x-c)
if len(anss)==0:print(-1)
else:print(min(anss)//2)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
n=int(input())
s=list(map(int,list(input()[:-1])))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
def f(lrc):
  l1,r1,c1,x1=lrc[0]
  for l2,r2,c2,x2 in lrc[1:]:
    l1,r1=max(max(l1,l2)-min(r1,r2),0),r1+r2
    if r1%2!=l1%2:l1+=1
    c1+=c2
    x1+=x2
  return [l1,r1,c1,x1]
def dfs(root,node):
  lrcx=[]
  for mode in edge[node]:
    if root!=mode:
      lrcx.append(dfs(node,mode))
  if len(lrcx)==0:
    return [s[node]]*4
  l,r,c,x=f(lrcx)
  c+=s[node]
  return [l+c,r+c,c,x+c]
anss=[]
for i in range(n):
  l,r,c,x=dfs(-1,i)
  if l==c:
    anss.append(x-c)
if len(anss)==0:print(-1)
else:print(min(anss)//2)
N = int(input())
s = N-1
for i in range(1, int(N**0.5) + 1):
    for j in range(1, int(N**0.5) + 1):
        if N == i * j:
            flag = i + j - 2

            if flag <= s:
                s = flag

print(s)

### FIXED CODE ###

A, B = map(int, input().split())
if (1 <= A <= 9) & (1 <= B <= 9):
    s = A*B
    print(s)

else:
    print(-1)
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for i in range(N)]
min_can = set()


def cal_score(bought_books):
    global CA
    global M
    global N
    global X
    algo_Q = [0]*M
    cost = 0
    for i in range(N):
        if bought_books[i] == 1:
            for j in range(1, M+1):
                algo_Q[j-1] += CA[i][j]
            cost += CA[i][0]
    flag = True
    for i in range(M):
        if algo_Q[i] < X:
            flag = False
            break
    if flag:
        global min_can
        min_can.add(cost)
    return 0


def next_book(book_list):
    global N
    global M

    if len(book_list) == N:
       return cal_score(book_list)
    book_list.append(0)
    next_book(book_list)
    book_list.pop(-1)

    book_list.append(1)
    next_book(book_list)
    book_list.pop(-1)
    return 0


book_list = []
next_book(book_list)
print(min(min_can))



### FIXED CODE ###

N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for i in range(N)]
min_can = set()


def cal_score(bought_books):
    global CA
    global M
    global N
    global X
    algo_Q = [0]*M
    cost = 0
    for i in range(N):
        if bought_books[i] == 1:
            for j in range(1, M+1):
                algo_Q[j-1] += CA[i][j]
            cost += CA[i][0]
    flag = True
    for i in range(M):
        if algo_Q[i] < X:
            flag = False
            break
    if flag:
        global min_can
        min_can.add(cost)
    return 0


def next_book(book_list):
    global N
    global M

    if len(book_list) == N:
       return cal_score(book_list)
    book_list.append(0)
    next_book(book_list)
    book_list.pop(-1)

    book_list.append(1)
    next_book(book_list)
    book_list.pop(-1)
    return 0


book_list = []
next_book(book_list)
if set() == min_can:
    print(-1)
else:
    print(min(min_can))
S = input()

if len(s) == 2:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s = str(input())

if len(s) == 2:
    print(s)
else:
    print(s[::-1])
def draw(i):
    global p,q,hd,wd
    B[p][q] = i
    if (q < W-1 and hd != -1):
        hd = 1
        wd = 0
    elif (hd == 1 and q == W-1) or (hd == -1 and q == 0):
        hd = 0
        wd = 1
    else:
        hd = -1
        wd = 0
    p += wd
    q += hd

if __name__ == '__main__':
    p = 0
    q = 0
    hd = 1
    wd = 0
    H, W = list(map(int, input().split()))
    N = int(input())
    As = list(map(int, input().split()))
    B = [[0 for i in range(W)] for j in range(H)]

    for i in range(N):
        for j in range(As[i]):
            draw(i+1)

    for i in range(H):
        s = list(map(str, B[i]))
        print(' '.join(s))




### FIXED CODE ###


def draw(i):
    global p,q,hd,wd
    B[p][q] = i
    if (q < W-1 and hd != -1):
        hd = 1
        wd = 0
    elif (hd == 1 and q == W-1) or (hd == -1 and q == 0):
        hd = 0
        wd = 1
    elif (q > 0 and hd != 1):
        hd = -1
        wd = 0
    p += wd
    q += hd

if __name__ == '__main__':
    p = 0
    q = 0
    hd = 1
    wd = 0
    H, W = list(map(int, input().split()))
    N = int(input())
    As = list(map(int, input().split()))
    B = [[0 for i in range(W)] for j in range(H)]

    for i in range(N):
        for j in range(As[i]):
            draw(i+1)

    for i in range(H):
        s = list(map(str, B[i]))
        print(' '.join(s))
n, a, b = map(int, input().split())

ans = n // (a + b)
ans *= a

if n % (a + b) != 0:
    ans += min(a, n % (a + b))

print(ans)

### FIXED CODE ###

s = input()

if "A" in s and "B" in s:
    print("Yes")
else:
    print("No")
N = int(input())
a = list(map(int, input().split()))
a.append(0)
pay = [0] * N
flag = True

for i in range(N):
    if(flag == False):
           flag = True
    for j in range(N + 1):
        if(flag == False):
           flag = True
           continue

        if(i == N - j - 1):
            if(N - j - 2 >= 0):
                pay[i] += abs(a[N - j] - a[N - j - 2])
                flag = False
            else:
                pay[i] += abs(a[N - j])
                flag = False
        else:
            if(N - j - 1 >= 0):
                pay[i] += abs(a[N - j] - a[N - j - 1])
            else:
                pay[i] += abs(a[N - j])
    
for i in range(N):
    print("{0}".format(pay[i]))

### FIXED CODE ###

pay = [int(input()) for i in range(4)]
# print(pay)
if(pay[0] < pay[1]):
    train = pay[0]
else:
    train = pay[1]
    
if(pay[2] < pay[3]):
    bus = pay[2]
else:
    bus = pay[3]

print("{0}".format(train + bus))
from collections import deque
import numpy as np
N,M = map(int,input().split(' '))
#G = {i:[] for i in range(1,N+1)}

GM = np.zeros((N,N)).astype(np.int)

for j in [0]*M:
	u,v = map(int,input().split(' '))
	GM[u-1,v-1] = 1
	#G[u].append(v)
S,T = map(int,input().split(' '))

G3M = np.dot(np.dot(GM,GM),GM)

#G3 = {i: np.where(G3M[i-1]>0)[0] for i in range(1,N+1)}

#dq =deque([S])
st = [S]
visited = [S]
ans = 1
exist = True
while(exist):
	new_st = []
	exist = False
	for cand in st:
		#for n in G3[cand]:
		ls = np.where(G3M[cand-1]>0)[0]
		for n in ls:
			n = n+1
			if n == T:
				print(ans)
				exit()
			if not n in visited:
				exist = True
				visited.append(n)
				new_st.append(n)
	st = new_st
	ans += 1
print(-1)









### FIXED CODE ###

import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N,M= map(int,input().split())
g = defaultdict(list)

for i in range(M):
    u,v = list(map(int,input().split()))
    g[u].append(N + v)
    g[N + u].append(2*N + v)
    g[2*N + u].append(v)
S,T= map(int,input().split())

dq = deque([S])
inf = 10**15
d = [inf for i in range(3*N+1)]
d[S] = 0

while dq:
    v = dq.popleft()
    for nv in g[v]:
        if d[nv] > d[v] + 1:
            d[nv] = d[v] + 1
            dq.append(nv)

if inf == d[T]:
    print(-1)
else:
    print(d[T]//3)
s=input()
l=[]

p=s[0]
seq=1

for c in s[1:]
  if c==p:
    seq+=1
  else:
    l.append(seq)
    seq=1
    p=c
ans=float("inf")

d1=min([a+b for a,b in zip(l[0::2],l[1::2])])
d2=min([a+b for a, b in zip(l[1::2],l[2::2])])
print(min(d1,d2))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

s = input()

K = float('inf')
if all(c == '0' for c in s):
    K = len(s)
elif all(c == '1' for c in s):
    K = len(s)
else:
    for k in range(1, len(s)):
        if s[k] != s[k-1]:
            K = min(K, max(k, len(s)-k))
        else:
            continue

print(K)
X=int(input())
if X>=1800:
  print(1)
elif X>=1600:
  print(2)
elif X>=1400:
  print(3) 
elif X>=1200:
  print(4)
elif X>=1000:
  print(5)
elif X>=800:
  print(6)
elif X>=600:
  print(7)
else:
  print(8)

elif X>=1600:
  print(2)  
  

### FIXED CODE ###

X=int(input())
if X>=1800:
  print(1)
elif X>=1600:
  print(2)
elif X>=1400:
  print(3) 
elif X>=1200:
  print(4)
elif X>=1000:
  print(5)
elif X>=800:
  print(6)
elif X>=600:
  print(7)
else:
  print(8)
count=0
def merge(A, left, mid, right):
    global count
    n1=mid - left
    n2=right - mid
    R=[]
    L=[]
    for i in range(n1):
        L.append(A[left+i])
    for i in range(n2):
        R.append(A[mid+i])
    L.append(100000001)
    R.append(100000001)
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)


### FIXED CODE ###

count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)
l1, l2, l3 = input() for _ in range(3)
print(l1[0]+l2[1]+l3[2])


### FIXED CODE ###

l1, l2, l3 = input(), input(), input()
print(l1[0]+l2[1]+l3[2])
a, b, c, d = map(int, input().split())
while True:
    c = c - b
    if c <= 0:
        print('Yes')
        break
    a = a - d
    if a <= 0:
        print('No')
        break


### FIXED CODE ###

s, w = map(int, input().split())
if s > w:
    print('safe')
else:
    print('unsafe')