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

import bisect

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

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""
AB.sort(key=lambda x: (-x[0], x[1]))

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append((a, b))
a0.sort()

nab.sort(key=lambda x: ((x[1] + 1) / x[0]))

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

dp = [[0] + [float('inf')] * 30 for _ in range(len(nab) + 1)]
for index, (a, b) in enumerate(nab):
    # print(a, b)
    for count in range(1, 31):
        dp[index + 1][count] = min(dp[index][count],
                                   dp[index][count - 1] + 1 + (dp[index][count - 1] + 1) * a + b)

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp[-1]):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)


### FIXED CODE ###

import bisect

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

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append(((b + 1) / a, a, b))
a0.sort()

nab.sort()

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

INF = 1 << 32
dp = [0] + [INF] * 29
for index, (_, a, b) in enumerate(nab):
    # print(a, b)
    ndp = [0] + [INF] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                         dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)
### BUGGY CODE ###

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

ans=0
MOD= 1000000007

c=[0]*(n+1)
c[0]=1
if 1 in a:
    c[1]=0
else:
    c[1]=1

for i in range(2,n+1):
    if i in a:
        continue
    else:
        c[i] = (c[i - 1] + c[i - 2]) % MOD

print(c[n]%MOD)

### FIXED CODE ###

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

INF=1000000007
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=INF
print(dp[n])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in a:
    ans = ans * i
if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
import sys
ans = 1
if 0 in a:
    print(0)
    sys.exit()
for i in a:
    if ans <= 1000000000000000000:
        ans = ans * i
      
    else:
        print(-1)
        sys.exit()
if ans <= 1000000000000000000:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import array

class Solver:

  def solve(self):
    n, k = map(int, raw_input().split())
    x = map(int, raw_input().split())
    y = [0] * (100100 - len(x))
    dp = array.array('i', [1<<30] * 100100)
    dp[0] = 0
    h = array.array('i', x + y)

    for i in xrange(n):
      for kk in xrange(k):
        j = kk + 1
        v = dp[i] + abs(h[i] - h[i+j])
        if dp[i+j] > v:
          dp[i+j] = v

    print dp[n-1]

Solver().solve()

### FIXED CODE ###

import array

class Solver:

  def solve(self):
    n, k = map(int, raw_input().split())
    x = map(int, raw_input().split())
    y = [0] * (100100 - len(x))
    dp = array.array('i', [1<<30] * 100100)
    dp[0] = 0
    h = array.array('i', x + y)

    for i in xrange(n):
      dpi = dp[i]
      hi = h[i]
      for kk in xrange(k):
        j = kk + 1
        v = dpi + abs(hi - h[i+j])
        if dp[i+j] > v:
          dp[i+j] = v

    print dp[n-1]

Solver().solve()
### BUGGY CODE ###

from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    number = 10 ** 5 * 2
    dists = [0] * number
    operations = number

    for ope_count in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        dists = accumulate(temp)
        if ope_count == 41:
            break

    print(*list(dists)[:-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for ope_count in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        templi = list(accumulate(temp))
        if templi == dists:
            break
        else:
            dists = templi

    print(*list(dists)[:-1])


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

N = int(input())
D = [int(x) for x in input().split()]
M = int(input())
T = [int(x) for x in input().split()]
flag = True
for i in T:
    if(i in D):
        D.pop(D.index(i))
    else:
        flag=False
if(flag):
    print('YES')
else:
    print('NO')


### FIXED CODE ###

N = int(input())
D = [int(x) for x in input().split()]
M = int(input())
T = [int(x) for x in input().split()]
flag = True
di = {}
for i in D:
    if(i in di):
        di[i]+=1
    else:
        di[i]=1
for i in T:
    if(i not in di):
        flag=False
        break
    elif(di[i]<=0):
        flag=False
        break
    else:
        di[i]-=1

if(flag):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import jit


@jit
def loop(N,K,A):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            temp = A[i]
            left = i - temp
            right = i + temp + 1
            if left < 0:
                left = 0
            if right > N:
                right = N
            B[left:right] += 1
        A = B
    return A


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    res = loop(N,K,A)

    print(*res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    return A


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    if K >= 43:
        M = 43
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()
### BUGGY CODE ###

N = int(input())
l = []
istwo = False
for i in range(N):
    a = int(input())
    if a == 2 and i != 1: istwo = True
    l.append(a-1)
flag = [0]*N
flag[0] = 1
flag[1] = 2
cnt = 0
cur_b = 0
while istwo:
    cnt += 1
    next_b = l[cur_b]
    if flag[next_b] == 1:
        print(-1)
        break
    elif flag[next_b] == 2:
        print(cnt)
        break
    else:
        flag[next_b] == 1
        cur_b = next_b

if istwo == False:
    print(-1)

### FIXED CODE ###

N = int(input())
l = [(int(input())-1) for _ in range(N)]
flag = [0]*N
flag[0] = 1
flag[1] = 2
cnt = 0
cur_b = 0
for i in range(N):
    cnt += 1
    next_b = l[cur_b]
    if flag[next_b] == 1:
        print(-1)
        break
    elif flag[next_b] == 2:
        print(cnt)
        break
    else:
        flag[next_b] == 1
        cur_b = next_b
else:print(-1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
from numba import jit

@jit
def Ed(num):
    ret=set()
    for i in range(1,int(num**0.5)+1):
        if num%i==0:
            ret.add(i)
            if num//i!=i:
                ret.add(num//i)
    return ret

@jit
def main():
    n=int(input().rstrip())
    ans=0
    a=sorted([int(i) for i in input().split()])
    for i in range(n):
        if i!=n-1:
            if a[i+1]==a[i]:continue
        yaku=Ed(a[i])
        for j in range(i):
            if a[j] in yaku:
                break
        else:
            #print(a[i])
            ans+=1
    print(ans)

if __name__=="__main__":main()

### FIXED CODE ###

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

N=int(input().rstrip())
a=[int(i) for i in input().split()]
l=max(a)+1
cnt=[0]*l
for i in a:
    for j in range(i,l,i):cnt[j]+=1

ans=0
for i in a:
    if cnt[i]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

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

box = [0] * 61
for i in range(n):
    s = bin (a[i])
    for j in range(len(s)-1):
        if s[-j] == '1':
            box[j] += 1
ans = 0
for i in range(1,61):
    ans += box[i] * (n - box[i]) * pow(2,i-1,10**9+7)
print(ans % (10**9+7))

### FIXED CODE ###

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

box = [0] * 61
for i in range(n):
    s = bin (a[i])
    for j in range(len(s)-1):
        if s[-j] == '1':
            box[j] += 1
ans = 0
for i in range(1,61):
    ans += box[i] * (n - box[i]) * pow(2,i-1,10**9+7)
print(ans % (10**9+7))
### BUGGY CODE ###

N, Q = map(int, input().split())
s = str(input())

t = []
d = []

for _ in range(Q):
    ti, di = map(str, input().split())
    t.append(ti)
    d.append(di)
    
LEFT_DIE = -1
RIGHT_DIE = N

def is_dead(i):
    for ti, di in zip(t, d):
        if s[i] == ti:
            if di == 'L':
                i -= 1
            if di == 'R':
                i += 1
            if i == LEFT_DIE:
                return LEFT_DIE
            if i == RIGHT_DIE:
                return RIGHT_DIE
    return 0

low = -1
high = N;
# LEFT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == LEFT_DIE:
        low = mid
    else:
        high = mid
left_edge = high

low = -1
high = N;
# RIGHT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == RIGHT_DIE:
        high = mid
    else:
        low = mid
right_edge = low

#print(left_edge, right_edge)
ans_s = s[left_edge:right_edge+1]
#print(ans_s)
ans = len(ans_s)
print(ans)

        
        
        
        
        
        

### FIXED CODE ###

N, Q = map(int, input().split())
s = str(input())

t = []
d = []

for _ in range(Q):
    ti, di = input().split()
    t.append(ti)
    d.append(di)
    
LEFT_DIE = -1
RIGHT_DIE = N

def is_dead(i):
    for ti, di in zip(t, d):
        if s[i] == ti:
            if di == 'L':
                i -= 1
            if di == 'R':
                i += 1
            if i == LEFT_DIE:
                return LEFT_DIE
            if i == RIGHT_DIE:
                return RIGHT_DIE
    return 0

low = -1
high = N;
# LEFT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == LEFT_DIE:
        low = mid
    else:
        high = mid
left_edge = high

low = -1
high = N;
# RIGHT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == RIGHT_DIE:
        high = mid
    else:
        low = mid
right_edge = low

#print(left_edge, right_edge)
ans_s = s[left_edge:right_edge+1]
#print(ans_s)
ans = len(ans_s)
print(ans)
### BUGGY CODE ###

n,k,*p=map(int,open(0).read().split())
l=[]
for i in range(n-k+1):
  sums=[]
  for j in p[i:i+k]:
    sums.append(j*(j+1)/(2*j))
  l.append(sum(sums))
print(max(l))
  

### FIXED CODE ###

n,k,*p=map(int,open(0).read().split())
s=sum(p[:k])  
l=[s]
for i in range(k,n):
  s=s-p[i-k]+p[i]
  l.append(s)
print((max(l)+k)/2)
### BUGGY CODE ###

import numpy as np


N,M=map(int,input().split())
# A=np.array(list(map(int,input().split())))
A=np.array(list(map(int,input().split())),dtype=np.int64)
A=np.sort(A)

EXC=[]

for i in range(M):
    exc=list(map(int,input().split()))
    EXC.append(exc)
excArry=np.array(EXC,dtype=np.int64)

col_num=1
Arr=excArry[np.argsort(excArry[:,col_num])[::-1]]
# print(A)
# print(Arr)

point=0


for j in range (M):
    # change_Num=Arr[j][1]
    count=np.count_nonzero(A<Arr[j][1])
    if count > 0:
        m=min(count,Arr[j][0])
        A[point:point+m]=Arr[j][1]
        point+=m
        # A=np.sort(A)
    else:
        break

print(np.sum(A))
    
#     for j in range (B):
#         count=np.count_nonzero(A<C)
#         if count>0:
#             m=min(B,count)
#             A[:m]=C
#         else:
#             continue
    
#     A=np.sort(A)

# print(np.sum(A))

### FIXED CODE ###

import numpy as np


N,M=map(int,input().split())
# A=np.array(list(map(int,input().split())))
A=np.array(list(map(int,input().split())),dtype=np.int32)
A=np.sort(A)

EXC=[]

for i in range(M):
    exc=list(map(int,input().split()))
    EXC.append(exc)
excArry=np.array(EXC,dtype=np.int32)

col_num=1
Arr=excArry[np.argsort(excArry[:,col_num])[::-1]]
# print(A)
# print(Arr)

point=0


for j in range (M):
    change_Num=Arr[j][1]
    count=np.count_nonzero(A<change_Num)
    if count > 0:
        m=min(count,Arr[j][0])
        A[point:point+m]=change_Num
        point+=m
        # A=np.sort(A)
    else:
        break

print(np.sum(A))
    
#     for j in range (B):
#         count=np.count_nonzero(A<C)
#         if count>0:
#             m=min(B,count)
#             A[:m]=C
#         else:
#             continue
    
#     A=np.sort(A)

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

N = int(input())
S = input()
Q = int(input())
K = [int(k) for k in input().split()]

def Counter(S, k):
    Total = 0
    count = [0, 0, 0] #D, M, DMの数
    for i in range(N):    
        if S[i] == "D": count[0] += 1
        elif S[i] == "M": 
            count[1] += + 1
            count[2] += count[0]
        elif S[i] == "C":
            Total += count[2]
        if i >= k - 1:
            if S[i-k+1] == "D":
                count[0] -= 1
                count[2] -= count[1]
            elif S[i-k+1] == "M":
                count[1] -= 1
    return Total

for i in range(Q):
    print(Counter(S, K[i]))

### FIXED CODE ###

N = int(input())
S = input()
Q = int(input())
K = [int(k) for k in input().split()]

def Counter(S, k):
    Total = 0
    count = [0, 0, 0] #D, M, DMの数
    for i in range(N):
        
        if S[i] == "D": count[0] += 1
        elif S[i] == "M": 
            count[1] += + 1
            count[2] += count[0]
        elif S[i] == "C":
            Total += count[2]
        if i >= k - 1:
            if S[i-k+1] == "D":
                count[0] -= 1
                count[2] -= count[1]
            elif S[i-k+1] == "M":
                count[1] -= 1
    return Total

for i in range(Q):
    print(Counter(S, K[i]))
### BUGGY CODE ###

ans = 1
n = input()
a = list(map(int,input().split()))
for i in a:
	ans = ans * i
if ans > 10**18:
	print("-1")
else:
	print(ans)

### FIXED CODE ###

ans = 1
n = input()
a = list(map(int,input().split()))
if 0 in a:
	ans = 0
for i in a:
	ans = ans * i
	if ans > 10**18:
		ans = -1
		break
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
u = 10**18
ans = 1
for i in a:
    ans *= i
if ans <= u:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int,input().split())))
u = 10**18
ans = 1
for i in a:
    ans *= i
    if i == 0:
        print(0)
        exit()
    if ans > u:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

aa = {}
for i in a:
  if i in aa:
    aa[i] += 1
  else:
    aa[i] = 1
 
for i in range(n):
  ans = 0
  aa[a[i]] -= 1
  for key in aa.keys():
    if aa[key] > 1:
      ans += comb(aa[key], 2)
  aa[a[i]] += 1
  print(ans)
  



### FIXED CODE ###

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

aa = [0 for i in range(2*10**5)]
for i in range(n):
  aa[a[i]] += 1
 
ans = 0
for key in range(2*10**5):
  ans += aa[key]*(aa[key]-1)//2
    
for i in range(n):
  tmp1 = aa[a[i]]*(aa[a[i]]-1)//2
  aa[a[i]] -= 1
  tmp2 = aa[a[i]]*(aa[a[i]]-1)//2
  aa[a[i]] += 1
  print(ans-tmp1 + tmp2)
### BUGGY CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    s = input()
    ans = 0
    for i in range(n-3):
        for j in range(i+1,n-1):
            for k in range(j+1,n):
                if j-i!=k-j:
                    if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                        ans += 1
    print(ans)
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    s = input()
    rgb = {"R":0,"G":0,"B":0}
    for i in s:
        rgb[i] += 1
    ans = 1
    for i in rgb.keys():
        ans *= rgb[i]
    for i in range(n-2):
        for j in range(i+1,n-1):
            k = j + (j-i)
            if k>=n:
                continue
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                ans -= 1
    print(ans)
    return

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

a, b, x = map(int, input().split())
count = 0

for i in range(a, b+1):
  if i % x == 0:
    count += 1

print(count)

### FIXED CODE ###

a, b, x = map(int, input().split())

nb = b // x + 1
na = (a-1) // x + 1 if a > 0 else 0

print(nb - na)
### BUGGY CODE ###

import queue

class Tree:
    def __init__(self, ind):
        self.children = []
        self.counter = 0
        self.index = ind
        self.parent = -1


N, Q = map(int, input().split(" "))
tree = [Tree(i) for i in range(N)]
ans = [0 for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split(" "))
    tree[a - 1].children.append(b - 1)
    tree[b - 1].children.append(a - 1)

for i in range(Q):
    p, x = map(int, input().split(" "))
    tree[p - 1].counter += x

# bfs
que = queue.Queue()
que.put(0)  # root is 0

while not que.empty():
    ind = que.get()
    ans[ind] = tree[ind].counter
    for child in tree[ind].children:
        if child == tree[ind].parent:
            continue
        tree[child].counter += tree[ind].counter
        tree[child].parent = ind
        que.put(child)

print(' '.join([str(a) for a in ans]))

### FIXED CODE ###

import queue
import sys
input = sys.stdin.readline

class Tree:
    def __init__(self, ind):
        self.children = []
        self.counter = 0
        self.index = ind
        self.parent = -1


N, Q = map(int, input().strip().split(" "))
tree = [Tree(i) for i in range(N)]
ans = [0 for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().strip().split(" "))
    tree[a - 1].children.append(b - 1)
    tree[b - 1].children.append(a - 1)

for i in range(Q):
    p, x = map(int, input().strip().split(" "))
    tree[p - 1].counter += x

# bfs
que = queue.Queue()
que.put(0)  # root is 0

while not que.empty():
    ind = que.get()
    ans[ind] = tree[ind].counter
    for child in tree[ind].children:
        if child == tree[ind].parent:
            continue
        tree[child].counter += tree[ind].counter
        tree[child].parent = ind
        que.put(child)

print(' '.join([str(a) for a in ans]))
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x: int(x) - 1, input().split())
    edge[u].append(v)
S, T = map(lambda x: int(x) - 1, input().split())


def dfs1(s, n, step):
    if step == 3:
        edge3[s].add(n)
    else:
        for e in edge[n]:
            dfs1(s, e, step + 1)


def bfs2(n):
    global T
    q = deque()
    status[n] = 0
    q.append(n)

    while len(q) > 0:
        v = q.popleft()
        for nv in edge3[v]:
            if status[nv] == -1:
                status[nv] = status[v] + 1
                q.append(nv)


edge3 = [set() for _ in range(N)]
for i in range(N):
    dfs1(i, i, 0)


status = [-1] * N
status[S] = 0
bfs2(S)
print(status[T])


### FIXED CODE ###

import sys
from collections import deque


data = sys.stdin.readlines()
N, M = map(int, data[0].split())
edge = [[] for _ in range(N)]
for i in range(1, M + 1):
    u, v = map(int, data[i].split())
    u -= 1
    v -= 1
    edge[u].append(v)
S, T = map(lambda x: int(x) - 1, data[M + 1].split())

visited = set()
q = deque()
q.append((0, S))
ans = 10 ** 10
while len(q) > 0:
    c, v = q.popleft()
    key = (c % 3, v)
    if key in visited:
        continue
    visited.add(key)
    if v == T and c % 3 == 0:
        ans = min(ans, c // 3)
    else:
        for e in edge[v]:
            newKey = (c + 1, e)
            q.append(newKey)

if ans == 10 ** 10:
    print(-1)
else:
    print(ans)