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

#!/usr/bin/python

import math
import sys

def is_prime(n):
    if n == 1:
        return False

    for i in xrange(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def main(argv):
    line = sys.stdin.readline()
    while line:
        Q = int(line.rstrip("\n"))
        for i in xrange(Q):
            l, r = map(
              lambda i: int(i), sys.stdin.readline().rstrip("\n").split(" "))

            counter = 0
            while l <= r:
                if is_prime(l) and is_prime((l + 1) / 2):
                    counter += 1
                l += 2
            print counter

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

### FIXED CODE ###

#!/usr/bin/python

import math
import sys

def is_prime(n):
    if n == 1:
        return False

    for i in xrange(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def main(argv):
    primes = [False]
    for i in xrange(1, 100000 + 1):
        primes.append(is_prime(i))

    counter = 0
    results = [0]
    for i in xrange(1, 100000 + 1):
        if i % 2 == 0:
            results.append(counter)
            continue

        if primes[i] and primes[(i + 1) / 2]:
            counter += 1
        results.append(counter)

    line = sys.stdin.readline()
    while line:
        Q = int(line.rstrip("\n"))
        for i in xrange(Q):
            l, r = map(
              lambda i: int(i), sys.stdin.readline().rstrip("\n").split(" "))

            print results[r] - results[l - 1]

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)
### BUGGY CODE ###

n = int(input())

for nn in range(1,n+1):
  ul = int(nn**0.5)+1
  cnt=0
  for i in range(1,ul):
    for j in range(1,ul):
      for k in range(1,ul):
        if i**2+j**2+k**2+i*j+j*k+k*i==nn:
          cnt+=1
  print(cnt)

### FIXED CODE ###

n = int(input())

from collections import defaultdict
d = defaultdict(int)

ul=int(n**0.5)

for i in range(1,ul):
  for j in range(1,ul):
    for k in range(1,ul):
      d[i**2+j**2+k**2+i*j+j*k+k*i]+=1
for j in range(1,n+1):
  print(d.get(j,0))
#  print(d[j] if d[j] else 0)
### BUGGY CODE ###

s = input()
count = 0

for i in range(0, len(s)-3):
    for j in range(i+4, len(s)+1):
        if int(s[i:j]) % 2019 == 0:
            count += 1

print(count)

### FIXED CODE ###

s = input()

MOD = 2019
d = [0] * MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i) * t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1

print(sum(i * (i - 1) // 2 for i in d))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

s = input()
n = len(s)
k = int(input())
ans = []
used = set()

for i in range(n):
    start = list(s[i])
    if s[i] not in used:
        ans.append(s[i])
        used.add(s[i])
    for j in range(i + 1, n):
        start.append(s[j])
        temp = "".join(start)
        if temp not in used:
            ans.append(temp)
            used.add(temp)
ans.sort()
print(ans[k - 1])


### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

s = input()
n = len(s)
k = int(input())
ans = []
used = set()
"""
from collections import defaultdict
d = defaultdict(list)
for i in range(n):
    d[s[i]].append(i)
""" 
for i in range(n):
    start = list(s[i])
    if s[i] not in used:
        ans.append(s[i])
        used.add(s[i])
    for j in range(i + 1, min(i + k, n)):
        start.append(s[j])
        temp = "".join(start)
        if temp not in used:
            ans.append(temp)
            used.add(temp)
ans.sort()
print(ans[k - 1])
### BUGGY CODE ###

import math
import sys
readline = sys.stdin.readline


def main():
    # input
    n = int(readline().rstrip())
    aList = list(map(int, readline().rstrip().split()))
    aAllList = set(aList)
    aConbiDic = {}
    aDic = {}
    aSum = 0
    for a in aAllList:
        aCount = aList.count(a)
        aDic[str(a)] = aCount
        aConbiDic[str(a)] = (aCount * (aCount - 1)) // 2
        aSum += (aCount * (aCount - 1)) // 2

    for a in aList:
        print(aSum - aDic[str(a)] + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import sys
readline = sys.stdin.readline


def main():
    # input
    n = int(readline().rstrip())
    A = list(map(int, readline().rstrip().split()))
    B = [0] * n

    for a in A:
        B[a - 1] += 1

    total = 0
    for b in B:
        if b > 1:
            total += b * (b - 1) // 2

    C = [0] * n
    for i, b in enumerate(B):
        C[i] = total + (b - 1) * (b - 2) // 2 - (b) * (b - 1) // 2

    for a in A:
        print(C[a-1])


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

n,m = map(int,input().split())
alis = list(map(int,input().split()))
lis = [list(map(int,input().split())) for x in range(m)]


for x in lis:
    alis.sort()
    alis = [x[1] if x[1]>alis[y] and y<x[0] else alis[y] for y in range(n)]
print(sum(alis))


### FIXED CODE ###

n,m = map(int,input().split())
alis = list(map(int,input().split()))
lis = [list(map(int,input().split())) for x in range(m)]
for x in alis:
    lis.append([1,x])
lis.sort(reverse=True,key=lambda x:x[1])
ans = 0
for x in lis:
    (number,point) = x
    if number >= n:
        number = n
        ans += number * point
        #print(n)
        #print(ans,'+=',number,'*',point)
        break
    ans += number * point
    n -= number
    #print(n)
    #print(ans,'+=',number,'*',point)
print(ans)
#print(lis)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = int(input())

ans = 1
for i in range(N):
    ans = ans * (i + 1)

# 大き過ぎる値を調整する
ans = ans % (10 ** 9 + 7) 

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())

ans = 1
for i in range(N):
    # 調整の処理は都度行っても端数の側に影響を与えないので問題ない
    ans = (ans * (i + 1)) % (10 ** 9 + 7) 

# 大き過ぎる値を調整する
# ans = ans % (10 ** 9 + 7) 

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

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    aaa = a.copy()
    aaa[i] = 0
    print(max(aaa))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_s = sorted(a, reverse=True)
a_max = a_s[0]
a_sec = a_s[1]
for i in range(n):
    if a[i] == a_max:
        print(a_sec)
    else:
        print(a_max)
### BUGGY CODE ###

n = int(input())
S = []
for _ in range(n):
    S.append(int(input()))
ans = 0
for i in range(1 << n):
    temp = 0
    for j in range(n):
        if (i >> j) & 1:
            temp += S[j]
    if temp % 10 == 0:
        temp = 0
    ans = max(temp, ans)
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline
n = int(input())
S = []
for _ in range(n):
    S.append(int(input()))
S.sort()
goukei = sum(S)
if goukei %10!=0:
    print(goukei)
    exit()
ans = 0
for i in range(n):
    temp = goukei - S[i]
    if temp % 10 == 0:
        temp = 0
    ans = max(ans, temp)

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

n=int(input())
data=list(map(int, input().split()))
count = 0
while(True):
  data = list(filter(lambda x: x%2==0, data))
  if len(data) < n:
    print(count)
    break
  else:
    count+=1

### FIXED CODE ###

n=int(input())
data=list(map(int, input().split()))
for i in range( max(data)):
  even_data = list(filter(lambda x: x%2==0, data))
  if len(even_data) < n:
    print(i)
    break
  data = list(map( lambda x: x / 2,  data))
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0

for i in A:
    for j in range(N):
        if i < B[j]:
            for k in range(N):
                if B[j] < C[k]:
                    ans += N - k
                    break

print(ans)

### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))

A.sort()
B.sort()

a = np.searchsorted(A, B, side='left')

B = sorted(B * (-1))
C = sorted(C * (-1))

c = np.searchsorted(C, B, side='left')
c = np.fliplr([c])[0]


print((a * c).sum())
### BUGGY CODE ###

def main():
  n,k=map(int,input().split())
  h=list(map(int,input().split()))+[0]*(k+10)
  dp=[(float("inf")) for i in range(n+k+10)]
  dp[0]=0
  for i in range(n-1):
    for j in range(k):
      dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
  return (dp[n-1])
print(main())


### FIXED CODE ###

def main():
  n,k=map(int,input().split())
  h=list(map(int,input().split()))+[0]*(k+10)
  dp=[(float("inf")) for i in range(n+k+10)]
  dp[0]=0
  for i in range(n-1):
    for j in range(k):
      dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
  return (dp[n-1])
print(main())
### BUGGY CODE ###

R,G,B,n = map(int,input().split())
c = 0
for r in range(n//R+1):
  for g in range(n//G+1):
    for b in range(n//B+1):
      if R*r + G*g + B*b == n:
        c += 1
        break
print(c)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
a = 0
for i in range(N//R+1):
  for j in range((N-R*i)//G+1):
    if (N-R*i-G*j) % B == 0:
      a += 1
print(a)
### BUGGY CODE ###

N = int(input())
S = list(str(input()))
from collections import Counter

def solve(idx, lis, dis):
    if len(lis)==1:
        i = lis[0]
        c = Counter(S[idx:])
        if len(S)>dis:
            if S[dis]==i:
                return c[i]-1
            else:
                return c[i]
        else:
            return c[i]
    elif len(lis)==2:
        ans = 0
        p, q = lis
        s = S[idx:]
        for i, j in enumerate(s):
            if j==p:
                ans += solve(i+idx, (q,), i*2+idx)
            elif j==q:
                ans += solve(i+idx, (p,), i*2+idx)
        return ans
    else:
        ans = 0
        p, q, r = lis
        for i, j in enumerate(S):
            if j==p:
                ans += solve(i, (q, r), i)
            elif j==q:
                ans += solve(i, (p, r), i) 
            elif j==r:
                ans += solve(i, (p, q), i) 
        return ans

print(solve(0, ('R', 'G', 'B'), 0))

### FIXED CODE ###

N = int(input())
S = list(str(input()))
from collections import Counter

c = Counter(S)
ans = c['B']*c['G']*c['R']
for i in range(N-1):
    for j in range(i, N):
        if S[i]==S[j]:
            continue
        elif i+(j-i)*2>N-1:
            break
        s = S[i+(j-i)*2]
        if s!=S[i] and s!=S[j]:
            ans -= 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))

tmp = 1
for i in range(K):
    tmp *= A[i]
tmp1 = tmp
idx = 0
for i in range(K, N):
    tmp1 *= A[i]
    tmp1 = tmp1//A[idx]
    if(tmp1 > tmp):
        print("Yes")
        tmp = tmp1
        idx += 1
    else:
        print("No")
        tmp = tmp1
        idx += 1

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))

idx = 0
for i in range(K, N):
    if(A[idx] < A[i]):
        print("Yes")
    else:
        print("No")
    idx += 1
### BUGGY CODE ###

import math


def f():
    n = int(input())
    a = list(map(int, input().split(" ")))
    b = []
    for i in range(len(a)):
        if i % 2 == 0:
            b.append(a[i])
        else:
            b.insert(0, a[i])
    if n % 2 == 1:
        b.reverse()
    b = list(map(str,b))
    print(" ".join(b))


f()


### FIXED CODE ###

import math


def f():
    n = int(input())
    a = list(map(int, input().split(" ")))
    b = []
    c = []
    for i in range(len(a)):
        if i % 2 == 0:
            b.append(a[i])
        else:
            c.append(a[i])
    c.reverse()
    d = c+b
    if n % 2 == 1:
        d.reverse()
    d = list(map(str,d))
    print(" ".join(d))


f()
### BUGGY CODE ###

N = int(raw_input())
A = map(int, raw_input().split())
ans = []
sum_all = sum(A) / 2

for i in range(0, N) :
    ic = sum_all
    for j in range(i+1, N, 2):
        ic -= A[j]
    for j in range(i-2, -1, -2):
        ic -= A[j]
    ans.append(ic*2)

print(' '.join(map(str, ans)))

### FIXED CODE ###

N = int(raw_input())
A = map(int, raw_input().split())
ans = []
sum_all = sum(A) / 2

ic = sum_all
for i in range(1, N, 2):
    ic -= A[i]
ans.append(ic*2)

for i in range(0, N-1):
    ans.append((A[i] - ans[i]/2)*2)

print(' '.join(map(str, ans)))
### BUGGY CODE ###

R,G,B,N= map(int,input().split())

cnt = 0

a = 3000//R
b = 3000//G
c = 3000//B
for i in range(0,a+1):
    for j in range(0,b + 1):
        if(R*i+G*j)<=N and (N-R*i - G*j )%B==0:

            cnt += 1
            # print(cnt)
        # if(R*i + G*j) < == N:
        #     cnt += (N-R*i + G*j )//B
        # # for k in range(0,c + 1):
        #     # if (R*i + G*j + B * k) == N:
        #     #     cnt += 1


print(cnt)


### FIXED CODE ###

R,G,B,N= map(int,input().split())

cnt = 0

a = 3000//R


for i in range(0,a+1):
    b = (3000-R*i)//G
    for j in range(0,b + 1):
        if(R*i+G*j)<=N and (N-R*i - G*j )%B==0:

            cnt += 1
            # print(cnt)
        # if(R*i + G*j) < == N:
        #     cnt += (N-R*i + G*j )//B
        # # for k in range(0,c + 1):
        #     # if (R*i + G*j + B * k) == N:
        #     #     cnt += 1


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

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
confo = [A[N-1]]
for i in range(N-1):
	ans += confo[0]
	confo.append(A[N-i-2])
	confo.append(A[N-i-2])
	del confo[0]
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
confo = [A[N-1]]
for i in range(N-1):
	ans += confo[i]
	confo.append(A[N-i-2])
	confo.append(A[N-i-2])
print(ans)
### BUGGY CODE ###

# coding:utf-8

import sys
from collections import defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, k = LI()

    G = defaultdict(list)
    AB = [LI_() for _ in range(n - 1)]
    for a, b in AB:
        G[a].append(b)
        G[b].append(a)

    def DFS(ss: list, t: int):
        # print([s + 1 for s in ss])
        q = deque()
        for s in ss:
            q.append((s, 0))
        visited = set(ss)
        cnt = 0
        while q:
            v, d = q.pop()
            visited.add(v)
            # print(v + 1, d)
            for to in G[v]:
                if to in visited:
                    continue
                if d + 1 > t:
                    cnt += 1
                q.append((to, d + 1))

        # print(cnt)
        return cnt

    # 木の性質
    # 直径をdとした時
    # dが偶数ならば，ある頂点vから他の頂点への距離がD/2となる頂点vが存在する
    # dが奇数ならば，ある辺eから他の頂点への距離が(D-1)/2となる辺eが存在する
    res = INF
    if k % 2:
        for a, b in AB:
            res = min(res, DFS([a, b], (k - 1) // 2))
    else:
        for i in range(n):
            res = min(res, DFS([i], k // 2))

    return res


print(main())


### FIXED CODE ###

# coding:utf-8

import sys
from collections import defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, k = LI()

    G = defaultdict(list)
    AB = [LI_() for _ in range(n - 1)]
    for a, b in AB:
        G[a].append(b)
        G[b].append(a)

    def DFS(ss: list, t: int):
        q = deque()
        for s in ss:
            q.append((s, 0))
        visited = [0] * n
        visited[ss[0]] = visited[ss[-1]] = 1
        while q:
            v, d = q.pop()
            if d >= t:
                continue
            for to in G[v]:
                if visited[to]:
                    continue
                visited[to] = 1
                q.append((to, d + 1))
        
        return n - sum(visited)

    # 木の性質
    # 直径をdとした時
    # dが偶数ならば，ある頂点vから他の頂点への距離がD/2となる頂点vが存在する
    # dが奇数ならば，ある辺eから他の頂点への距離が(D-1)/2となる辺eが存在する
    res = INF
    if k % 2:
        for a, b in AB:
            res = min(res, DFS([a, b], (k - 1) // 2))
    else:
        for i in range(n):
            res = min(res, DFS([i], k // 2))

    return res


print(main())
### BUGGY CODE ###

#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

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

for i in range(M):
    B,C = map(int, input().split())
    A += [C]*B

A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

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

L = []
for i in range(M):
    l = list(map(int, input().split()))
    L.append(l)
L = sorted(L, key=lambda x:-x[1])

ans = 0
index = 0
for i in range(N):
    if index >= M:
        ans += A[i]
    else:
        if A[i] >= L[index][1]:
            ans += A[i]
        else:
            ans += L[index][1]
            L[index][0] -= 1
            if L[index][0] == 0:
                index += 1

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

n,m,q=map(int,input().split())
g=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a][b]+=1
r=[[0 for i in range(n+1)] for j in range(n)]
for i in range(n):
    for j in range(1,n+1):
        r[i][j]=r[i][j-1]+g[i][j-1]
for i in range(q):
    a,b=map(int,input().split())
    a-=1
    b-=1
    ans=0
    for i in range(a,b+1):
        ans+=r[i][b+1]-r[i][a]
    print(ans)


### FIXED CODE ###

n,m,q=map(int,input().split())
g=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    #a-=1
    #b-=1
    g[a][b]+=1
    
for i in range(n):
    for j in range(n+1):
        g[i+1][j]+=g[i][j]
for i in range(n+1):
    for j in range(n):
        g[i][j+1]+=g[i][j]
for i in range(q):
    a,b=map(int,input().split())
    a-=1
    print(g[b][b]+g[a][a]-g[a][b]-g[b][a])
#print(g)
### BUGGY CODE ###

# ABC136 C - Build Stairs

n = int(input())
h = list(map(int,input().split()))
for i in range(len(h)-1):
    if h[i] - min(h[i+1:]) >= 2:
        print('No')
        exit()
print('Yes')

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
base=0
for h in H:
    if base>h:
        print("No")
        break
    base=max(base,h-1)
else:
    print("Yes")
### BUGGY CODE ###

N = input()
H = input().split()
count = 0
if 1 <= int(N) and int(N) <= 10**5:

    for i in range(int(N)-1):
        # print(H[i])
        tmp = 0
        h = int(H[i])
        if 1 <= h and h <= 10**9:
            # print("答え")
            for j in range(i+1, int(N)):
                hn = int(H[j])
                if 1 <= hn and hn <= 10**9:
                    
                    if h >= hn:
                        tmp += 1
                        h = hn
                    else:
                        break
            
            if tmp > count:
                count = tmp
    print(count)

### FIXED CODE ###

N = input()
H = input().split()
count = 0

if not(1 <= int(N) and int(N) <= 10**5):
    exit()
for h in H:
    if not(1 <= int(h) and int(h) <= 10**9):
        exit()

tmp = []

for i in range(int(N)-1):
    if int(H[i]) >= int(H[i+1]):
        tmp.append(1)
    else:
        tmp.append(0)

# print(tmp)
count = 0
c = 0
for i in tmp:
    if i == 1:
        c += 1
    else:
        # print(c)
        if c >= count:
            count = c
        c = 0
if c > count:
    print(c)
else:
    print(count)
### BUGGY CODE ###

n = int(input())
an = [int(input()) for _ in range(n)]
    
for i in range(n):
        an_i= an[i]
        an[i] = 0
        print(max(an))
        an[i] = an_i

### FIXED CODE ###

n = int(input())
an = []
max_1 = 1
max_2 = 1
count = 1
max1_index = [0]
for i in range(n):
    a = int(input())
    if a > max_1:
        tmp = max_1
        max_1 = a
        count = 1
        max1_index = [i]
        max_2 = tmp
    elif a == max_1:
        count += 1
        max1_index.append(i)
    elif max_1 >  a > max_2:
        max_2 = a
    an.append(a)
if count == 1:
    for i in range(n):
        if i in max1_index:
            print(max_2)
        else:
            print(max_1)
else:
    for i in range(n):
        print(max_1)
### BUGGY CODE ###

from collections import defaultdict 

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

if M == 0:
  print(-1)
  exit()

INF = 10**6
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

to1d={v:{} for v in range(N)}
count=2
for p,q,c in pqc:
  if not to1d[p].get(c):
    to1d[p][c] = count
    count += 1
  if not to1d[q].get(c):
    to1d[q][c] = count
    count += 1

G = [{} for _ in range(count)]
for p,q,c in pqc:
  v1,v2 = to1d[p][c],to1d[q][c]
  G[v1][v2] = G[v2][v1] = 0
  
for v in range(N):
  if len(to1d[v])>1:
    tmp = list(to1d[v].keys())
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1
        
def dijkstra(start = 0, goal = 1):
    from heapq import heappop, heappush
    d = [INF]*len(G)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
        if v == goal: return d[goal]
    return d[goal]

for c in to1d[0].keys():
  v = to1d[0][c]
  G[0][v] = 1
for c in to1d[N-1].keys():
  v = to1d[N-1][c]
  G[v][1] = 0
  
ans = dijkstra(0,1)
print(ans if ans < INF else -1)

### FIXED CODE ###

def main():
  N,M=map(int,input().split())

  if M == 0:
    print(-1)
    exit()

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(N+count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for i in range(N):
    if len(to1d[i])<=1: continue
    for c in to1d[i].keys():
      v = to1d[i][c]
      G[v][count] = 1
      G[count][v] = 0
    count += 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()