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

N = int(input())
K = [int(i) for i in input().split()]

ans = 1
burst = False
zero = False
for k in K:
    if k == zero:
        zero = True
        break
    ans *= k
    if ans > 10**18:
        burst = True
if zero:
    print(0)
elif burst:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N = int(input())
K = [int(i) for i in input().split()]

if K.count(0) > 0:
    print(0)
else:
    ans = 1
    burst = False
    for k in K:
        ans *= k
        if ans > 10**18:
            burst = True
            break
    if burst:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
 
a_list=[]
 
for index in range(m):
    a_list.append(int(input()))
 
ans_list=[]
 
for index in range(n + 1):
    ans_list.append(0)
 
for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_list):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_list:
        if (index - 1) not in a_list:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_list:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007
 
print(ans_list[n])


### FIXED CODE ###

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

a_set=set()

for index in range(m):
    a_set.add(int(input()))

ans_list=[]

for index in range(n + 1):
    ans_list.append(0)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])
### BUGGY CODE ###

import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]

queue = []
# sy,sx = 0,0
# gy,gx = H-1,W-1
for i in range(H):
    for j in range(W):
        if field[i][j] == True:
            queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = []
    while queue:
        h,w = queue.pop(0)
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] != '#':
                    if field[nh][nw] == False:
                        field[nh][nw] = True
                        nqueue.append([nh,nw])
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)
    

### FIXED CODE ###

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

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

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

pair = n*(n - 1)/2
not_4 = 0
ans = 'Yes'
num = len(a)
for i in range(num):
  if a[i] == 4:
    continue
  else:
    for j in range(num):
    
      if i != j and a[i]*a[j]%4 != 0:
        not_4 += 1
      
        if not_4 >= pair:
          ans = 'No'
          break
    
print(ans)

### FIXED CODE ###

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

four = 0
two = 0
one = 0
for i in a:
  if i%4 == 0:
    four += 1
  elif i%2 == 0 and i%4 != 0:
    two += 1
  elif i%2 != 0:
    one += 1

if four >= one or four + 1 >= two//2 + two%2 + one or n == two:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

def main():
    import heapq
    n,k = map(int,input().split(" "))
    q = []
    for i in range(n):
        a,b = map(int,input().split(" "))
        for j in range(b):
            heapq.heappush(q,a)
    
    for i in range(k):
        m = heapq.heappop(q)
    
    print(m)
main()

### FIXED CODE ###


def main2():
    import heapq
    n,k = map(int,input().split(" "))
    q = []
    for i in range(n):
        a,b = map(int,input().split(" "))
        heapq.heappush(q,(a,b))
    
    while k>0:
        a,b = heapq.heappop(q)
        k-=b
    
    print(a)
main2()
### BUGGY CODE ###

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

for i in range(N):
    tmp = A[i]
    A[i] = -1
    print(max(A))
    A[i] = tmp

### FIXED CODE ###

import copy

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

res = sorted(A,reverse=True)
for i in range(N):
    if A[i] == res[0]:
        print(res[1])
    else:
        print(res[0])
### BUGGY CODE ###

import numpy as np
A, B = map(int, input().split())
bins = np.array([list(map(int, list('{number:0>40}'.format(number=bin(i)[2:])))) for i in range(A, B+1)]).T
bins = np.sum(bins, axis=1) % 2
result = 0
for d, i in enumerate(bins[::-1]):
    if i == 1:
        result += 2 ** d
print(result)

### FIXED CODE ###

A, B = map(int, input().split())
if A % 2 == 0:
    num = B - A
    result = 0
else:
    num = (B - (A + 1))
    result = A
if num // 2 % 2 == 0:
    result ^= 0
else:
    result ^= 1
if num % 2 == 1:
    result ^= (B-1)
result ^= B
print(result)
### BUGGY CODE ###

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

max = max(a)
ans = 10000000
for b in range(max*-1,max):
  sum = 0
  for i, j in enumerate(a):
    i = i+1
    sum += abs(j - (b+i))
  if ans > sum:
    ans = sum

print(ans)

### FIXED CODE ###

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

b = []

for i in range(n):
  b.append(a[i]-(i+1))

# print(b)
b.sort()
# print(b)

min_b=b[n//2]
# print(min_b)

ans = 0
for i in range(n):
  ans+=abs(a[i]-(min_b+(i+1)))
  # print(ans)
print(ans)
### BUGGY CODE ###

mod = 10**9+7


def mat_mul(A, B):
    # A,Bは正方行列とする
    C = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = sum(A[i][k] * B[k][j] for k in range(N)) % mod
    return C


def matpow(A, n):
    B = [[0]*N for _ in range(N)]
    for i in range(N):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = mat_mul(A, B)
        A = mat_mul(A, A)
        n //= 2
    return B


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    A = matpow(A, K)
    ans = 0
    for a in A:
        ans = (ans + sum(a)) % mod
    print(ans)


### FIXED CODE ###

mod = 10**9+7


def mat_mul(A, B):
    # A,Bは正方行列とする
    C = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = sum(A[i][k] * B[k][j] for k in range(N)) % mod
    return C


def matpow(A, n):
    B = [[0]*N for _ in range(N)]
    for i in range(N):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = mat_mul(A, B)
        A = mat_mul(A, A)
        n //= 2
    return B


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    A = matpow(A, K)
    ans = 0
    for a in A:
        ans = (ans + sum(a)) % mod
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = [lmis() for _ in range(N)]
    @lru_cache(maxsize=None)
    def rec(h):
        if h <= 0:
            return 0
        return min(rec(h-a)+b for a, b in AB)
    print(rec(H))

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    DP = [INF] * (H+1)
    DP[0] = 0
    for h in range(1, H+1):
        for i in range(N):
            DP[h] = min(DP[h], (DP[h-AB[i][0]]+AB[i][1] if h-AB[i][0]>0 else AB[i][1]))

    print(DP[-1])

main()
### BUGGY CODE ###

import copy
n,m,q=map(int,input().split())
List=[]
for i in range(q):
  a,b,c,d=map(int,input().split())
  List.append([a,b,c,d])
List.sort()
s=-1
for i in range(2 ** q):
    l=[-1]*9
    l.insert(0,1)
    l.insert(0,1)
    point=0
    for j in range(q):
      if ((i >> j) & 1):
        point+=List[j][3]
        if l[List[j][0]]!=-1 and l[List[j][1]]!=-1 and l[List[j][1]]-l[List[j][0]]!=List[j][2]:
          l[0]=-2
          break
        else:
          if l[List[j][0]]==-1 and l[List[j][1]]!=-1:
            l[List[j][0]]=l[List[j][1]]-List[j][2]
          elif l[List[j][0]]!=-1 and l[List[j][1]]==-1:
            l[List[j][1]]=l[List[j][0]]+List[j][2]
          elif l[List[j][0]]==-1 and l[List[j][1]]==-1:
            if l[List[j][1]]!=l[List[j][1]]+List[j][2]:
              l[0]=-2
              break
    ll = [k for k in l if k != -1]
    if 1<=min(ll) and max(ll)<=m:
          x=copy.deepcopy(ll)
          x.sort()
          if x==ll and point>s:
            s=point
print(s)

### FIXED CODE ###

import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b,c=mi()
l=[list(mi()) for i in range(c)]
x=list(itertools.combinations_with_replacement(range(1,b+1),a))
ans=0
for j in x:
  c=0
  for i in l:
    if j[i[1]-1]-j[i[0]-1]==i[2]:
      c+=i[3]
  if c>ans:
    ans=c
print(ans)
### BUGGY CODE ###

from sys import stdin
import sys

l = stdin.readline().rstrip().split(' ')
a = stdin.readline().rstrip().split(' ')
b = stdin.readline().rstrip().split(' ')
k = int(l[2])
n = int(l[0])
m = int(l[1])
ia = 0
ib = 0
b_sum = 0
count = 0
a_sum = 0
res = []

for ib in range(m):
    b_sum += int(b[ib])
    if b_sum <= k:
        count += 1
    else:
        break
res.append(count)
count = 0
for ia in range(n):
    a_sum = a_sum + int(a[ia])
    if k < a_sum:
        #print("ok")
        res.append(count)
        continue
    else:
        count = ia + 1
    b_sum = a_sum
    for ib in range(m):
        b_sum += int(b[ib])
        if b_sum <= k:
            count += 1
        else:
            break
    res.append(count)
print(max(res))

### FIXED CODE ###

from sys import stdin
import sys

l = stdin.readline().rstrip().split(' ')
A = list(map(int, input().split()))
B = list(map(int, input().split()))
k = int(l[2])
n = int(l[0])
m = int(l[1])

sum = 0
a = [0]
for i in range(n):
    sum += A[i]
    a.append(sum)
sum = 0

b = [0]
for i in range(m):
    sum += B[i]
    b.append(sum)
#print(b)

ans = 0
j = 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)
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[None]*h
for i in range(h):
  grid[i]=input()
  
L=[[0 for i in range(w)] for j in range(h)]
R=[[0 for i in range(w)] for j in range(h)]
U=[[0 for i in range(w)] for j in range(h)]
D=[[0 for i in range(w)] for j in range(h)]

for i in range(h):
  if grid[i][0]=="#":
    L[i][0]=0
  else:
    L[i][0]=1
  for l in range(1,w):
    if grid[i][l]=="#":
      L[i][l]=0
    else:
      L[i][l]=L[i][l-1]+1
      
  if grid[i][-1]=="#":
    R[i][-1]=0
  else:
    R[i][-1]=1
  for r in range(w-2,-1,-1):
    if grid[i][r]=="#":
      R[i][r]=0
    else:
      R[i][r]=R[i][r+1]+1
      
for j in range(w):
  if grid[0][j]=="#":
    U[0][j]=0
  else:
    U[0][j]=1
  for u in range(1,h):
    if grid[u][j]=="#":
      U[u][j]=0
    else:
      U[u][j]=U[u-1][j]+1
      
  if grid[-1][j]=="#":
    D[-1][j]=0
  else:
    D[-1][j]=1
  for d in range(h-2,-1,-1):
    if grid[d][j]=="#":
      D[d][j]=0
    else:
      D[d][j]=D[d+1][j]+1
      
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j])

print(ans-3)


### FIXED CODE ###

h,w=map(int,input().split())
grid=[None]*h

for i in range(h):
  grid[i]=input()

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]

for i in range(h):
  s=grid[i]
  left=0
  right=0
  while left<len(s):
    if s[left]=="#":
      left+=1
      right=left
      continue
    while right+1<w and s[right+1]==".":
      right+=1
  
    for j in range(left,right+1):
      yoko[i][j]=right-left
      
    left=right+1
    right=left
    
for i in range(w):
  up=0
  down=0
  while up<h:
    if grid[down][i]=="#":
      up+=1
      down=up
      continue
    while down+1<h and grid[down+1][i]==".":
      down+=1
    for j in range(up,down+1):
      tate[j][i]=down-up
    up=down+1
    down=up
    
ans=0
for i in range(h):
  for j in range(w):
    if grid[i][j]==".":
      ans=max(ans,tate[i][j]+yoko[i][j])
      
print(ans+1)
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]==S[j]: continue
        for k in range(j+1,N):
            if (j-i!=k-j) and (S[i]!=S[k]) and (S[j]!=S[k]):
                ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()

r,g,b=0,0,0
for s in S:
    if s=='R': r+=1
    elif s=='G': g+=1
    else: b+=1


ng=0
for i in range(N):
    for j in range(i+1,N):
        k=j+(j-i)
        if k>=N: continue
        if S[i]!=S[j] and S[j]!=S[k] and S[i]!=S[k]:
            ng+=1

ans=r*g*b
print(ans-ng)
### BUGGY CODE ###

import numpy as np
n = int(input())
ans = 0
field = [list(map(int,input().split())) for _ in range(n)]
dp = np.zeros((n + 1,3),np.int64)
for i in range(n):
  for j in range(3):
    for k in range(3):
      if j == k:
        continue
      dp[i + 1][k] = max(dp[i + 1][k],dp[i][j] + field[i][k])
for d in dp[-1]:
  ans = max(ans,d)
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
ans = 0
field = [map(int,input().split()) for _ in range(n)]
x,y,z = 0,0,0
# 1つ前の値のみわかればよいので
# aにはa,a,aがbには
for a,b,c in field:
  #x,y,zは毎回入れ替わるので活動は連続しない
  x,y,z = max(y,z) + a,max(x,z) + b,max(x,y) + c

print(max(x,y,z))
### BUGGY CODE ###

import copy

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['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']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=[[[] for i in range(0,N)] for j in range(0,M)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[0][i]=[t[0]]

for i in range(0,M):
    for j in range(0,N):
        x=t[i]
        if index[x] and j>=index[x][0]:
            start=0
            end=len(index[x])-1
            while end-start>1:
                test=(end+start)//2
                if j>=index[x][test]:
                    start=test
                else:
                    end=test
            if j>=index[x][end]:
                next=index[x][end]-1
            else:
                next=index[x][start]-1
            if next>=0:
                if len(dp[i-1][j])>1+len(dp[i-1][next]):
                    dp[i][j]=dp[i-1][j]
                else:
                    x=copy.copy(dp[i-1][next])
                    x.append(t[i])
                    dp[i][j]=x
            else:
                if dp[i-1][j]==[]:
                    dp[i][j]=[t[i]]
                else:
                    dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=dp[i-1][j]

print(''.join(dp[M-1][N-1]))

### FIXED CODE ###

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['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']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M+1)] for i in range(0,N+1)]

for i in range(0,N):
    for j in range(0,M):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]

ans=[]
i=N
j=M
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans.append(s[i-1])
        i-=1
        j-=1

ans=ans[::-1]
print(''.join(ans))
### BUGGY CODE ###

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

def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list

amax = M // N
L = make_divisor_list(M)
L = [i for i in L if i <= amax]

if M % N == 0:
    ans = int(M/N)
else:
    for i in L[::-1]:
        if (M - (i * N)) % i == 0:
            ans = i
            break

print(ans)


### FIXED CODE ###

import math

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

# N = 100000
# M = 1000000000

def pfac(n):
    values = [1, n]
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            values.append(i)
            values.append(n // i)
    return values

L = pfac(M)
L = [i for i in L if i * N <= M]

ans = []

for i in L[::-1]:
    # if (M - (N * i)) % i == 0:
    if M % i == 0:
        ans.append(i)

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

import sys
N = int(input())
lists = [int(i) for i in input().split()]
sok = sys.maxsize
list2 = [xx - max(lists) for xx in range (2 * max(lists) + 1)]
for b in list2:
    kanashi = 0
    i = 1
    for x in lists:
        kanashi += abs(x - (b + i))
        i += 1
    if (kanashi < sok):
        sok = kanashi
print(sok)


### FIXED CODE ###

def med(data):
    N = len(data)
    data.sort()
    if N % 2 == 0:
        median1 = N/2
        median2 = N/2 + 1
        median1 = int(median1) - 1
        median2 = int(median2) - 1
        median = (data[median1] + data[median2]) / 2
        return median
    else:
        median = (N + 1) / 2
        median = int(median) - 1
        median = data[median]
        return median

import sys
N = int(input())
lists = [int(i) for i in input().split()]
sok = sys.maxsize
list2 = [x - j - 1 for j, x in enumerate(lists)]
b = med(list2)
kanashi = 0
for xx in list2:
    kanashi += abs(xx - b)
print(int(kanashi))
### BUGGY CODE ###

n = int(input())
s = input()
ans = ""
curr_set = ""
for i in range(n):
    if s[i] == curr_set:
        continue
    else:
        curr_set = s[i]
        ans=ans+s[i]
print(len(ans))

    


### FIXED CODE ###

n = int(input())
s = raw_input()
ans = 0
curr_set = ""
for i in range(n):
    if s[i] == curr_set:
        continue
    else:
        curr_set = s[i]
        ans+=1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq
INF = 10**9

n, m = map(int, input().split())
pqc = []

seen = set()
for i in range(n):
    seen.add((i, 0))
for _ in range(m):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1
    pqc.append((p, q, c))
    seen.add((p, c))
    seen.add((q, c))
comp = dict()
for i, node in enumerate(seen):
    comp[node] = i

edge = [[] for _ in range(len(comp))]
for key in comp.keys():
    v, c = key
    if c != 0:
        frm = comp[(v, c)]
        too = comp[(v, 0)]
        edge[frm].append((too, 0))
        edge[too].append((frm, 1))

for p, q, c in pqc:
    frm = comp[(p, c)]
    too = comp[(q, c)]
    edge[frm].append((too, 0))
    edge[too].append((frm, 0))

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

DIJK = Dijkstra(edge)
DIJK.calc(comp[(0, 0)])
ans = DIJK.dist[comp[(n-1, 0)]]
if ans == INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque
INF = 10**9

n, m = map(int, input().split())
pqc = []

seen = set()
for i in range(n):
    seen.add((i, 0))
for _ in range(m):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1
    pqc.append((p, q, c))
    seen.add((p, c))
    seen.add((q, c))
comp = dict()
for i, node in enumerate(seen):
    comp[node] = i

edge = [[] for _ in range(len(comp))]
for key in comp.keys():
    v, c = key
    if c != 0:
        frm = comp[(v, c)]
        too = comp[(v, 0)]
        edge[frm].append((too, 0))
        edge[too].append((frm, 1))

for p, q, c in pqc:
    frm = comp[(p, c)]
    too = comp[(q, c)]
    edge[frm].append((too, 0))
    edge[too].append((frm, 0))

class BFS:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = deque()

    def calc(self, start):
        self.dist[start] = 0
        self.q.append((0, start))
        while len(self.q) != 0:
            prov_cost, src = self.q.popleft()
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    if cost == 1:
                        self.q.append((self.dist[dest], dest))
                    else:
                        self.q.appendleft((self.dist[dest], dest))
        return self.dist

bfs = BFS(edge)
bfs.calc(comp[(0, 0)])
ans = bfs.dist[comp[(n-1, 0)]]
if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###


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

cnt=0

for i in range(n):
    if min(p[:i+1])>=p[i]:
        cnt+=1
    else:
        continue

print(cnt)

### FIXED CODE ###

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

cnt=0
min_val=p[0]

for i in range(n):
    if min_val>=p[i]:
        min_val=p[i]
        cnt+=1
    else:
        continue

print(cnt)
### BUGGY CODE ###

import collections
text = input()
candidates = []
m = len(text)
for i in range(m-1):
  for j in range(i+1,m):
    target = text[i:j+1]
    c = collections.Counter(target)
    mc = c.most_common()
    if mc[0][1]>(j-i+1)//2:
      print(i+1,j+1)
      exit()
print('-1 -1')

### FIXED CODE ###

S = input()
for i in range(len(S)-2):
  for j in [i+1,i+2]:
    if S[i] == S[j]:
      print(i+1,j+1)
      exit()
if len(S) == 2 and S[0]==S[1]:
  print(1,2)
  exit()
print('-1 -1')