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

import math

A,B,N=map(int,input().split())

def floor_t(A,B,y):
    return math.floor(A*y/B) - A*math.floor(y/B)

total = 0

# if A==B:
#     if A-1<=N:
#         print(floor_t(A,B,A-1))
#         exit(0)
#     else:
#         print(floor_t(A,B,N))
#         exit(0)

for x in range(N+1):
    if x%B==0:
        continue
    else:
        total = max(total,floor_t(A,B,x))

print(total)



### FIXED CODE ###

import math

A,B,N=map(int,input().split())

def floor_t(A,B,y):
    return math.floor(A*y/B) - A*math.floor(y/B)

#関数の挙動を調べる
# for x in range(1,10*B+1):
#     print('x={} : floor(AX/B)={}'.format(x,math.floor(A*x/B)))

# for x in range(1,10*B+1):
#     print('x={} : floor(X/B)={}'.format(x,A*math.floor(x/B)))

# for i in range(1,10*B+1):
#     print('x={}:f(x)={}'.format(i,floor_t(A,B,i)))

X=min(N,B-1)

print(floor_t(A,B,X))
### BUGGY CODE ###

import bisect
import sys
input=sys.stdin.readline
def main():
    N=int(input())
    S=input().rstrip()
    R,G,B=[],[],[]
    for i in range(N):
        if S[i]=='R':
            R.append(i)
        elif S[i]=='G':
            G.append(i)
        elif S[i]=='B':
            B.append(i)
    ans=0
    for i in range(N):
        for j in range(i):
            if(S[i]==S[j]):
                continue
            else:
                s=set([S[i],S[j]])
            if('B' not in s):
                lon=len(B)-bisect.bisect_left(B,i)
                mi=bisect.bisect_left(B,i+i-j)
                if(mi<len(B) and B[mi]==i+i-j):
                    lon-=1
            elif('R' not in s):
                lon=len(R)-bisect.bisect_left(R,i)
                mi=bisect.bisect_left(R,i+i-j)
                if(mi<len(R) and R[mi]==i+i-j):
                    lon-=1
            elif('G' not in s):
                lon=len(G)-bisect.bisect_left(G,i)
                mi=bisect.bisect_left(G,i+i-j)
                if(mi<len(G) and G[mi]==i+i-j):
                    lon-=1
            ans+=lon
        
    print(ans)
    
if __name__=='__main__':
    main()

### FIXED CODE ###

import bisect
import sys
input=sys.stdin.readline
def main():
    N=int(input())
    S=input().rstrip()
    R,G,B=[],[],[]
    for i in range(N):
        if S[i]=='R':
            R.append(i)
        elif S[i]=='G':
            G.append(i)
        elif S[i]=='B':
            B.append(i)
    ans=0
    for i in range(N):
        for j in range(i):
            if(S[i]==S[j]):
                continue
            s=set([S[i],S[j]])
            if('B' not in s):
                lon=len(B)-bisect.bisect_left(B,i)
                mi=bisect.bisect_left(B,i+i-j)
                if(mi<len(B) and B[mi]==i*2-j):
                    lon-=1
            elif('R' not in s):
                lon=len(R)-bisect.bisect_left(R,i)
                mi=bisect.bisect_left(R,i+i-j)
                if(mi<len(R) and R[mi]==i*2-j):
                    lon-=1
            elif('G' not in s):
                lon=len(G)-bisect.bisect_left(G,i)
                mi=bisect.bisect_left(G,i+i-j)
                if(mi<len(G) and G[mi]==i*2-j):
                    lon-=1
            ans+=lon
        
    print(ans)
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())

n = I()
s = list(S())
sj = s[1:]

c = 0
for i in s:
    sk = sj[1:]
    if len(sk) <= 0:
        break
    cj = 0
    for j in sj:
        cj += 1
        if len(sk) <= 0:
            break
        if i != j:
            ck = 0
            for k in sk:
                ck += 1
                if i!=k and j!=k and cj != ck:
                    c += 1
        sk.pop(0)
    sj.pop(0)

print(c)

### FIXED CODE ###

from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
 
n = I()
s = list(S())

r = s.count('R')
g = s.count('G')
b = s.count('B')
 
ans = r*g*b
for i in range(n-1):
    for j in range(1,n):
        if i-j<0 or n<=i+j:
            break
        else:
            if s[i-j]!=s[i] and s[i]!=s[i+j] and s[i-j]!=s[i+j]:
                ans-=1
 
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a = list(map(int,input().split()))
rep = []
rep.append(1)
i = 0
cnt = 0
if n>k:
    end =k
else:
    end =n
nof = 0
while True:
    cnt+=1
    if cnt>end:
        nof=1
        break
    go = a[i]-1
    if a[i] not in rep:
        rep.append(a[i])
        i = go
    else:
        rep.append(a[i])
        break
if nof==1:
    print(rep[k])
else:
    lr = len(rep)
    for i in range(lr):
        if rep[i]==rep[lr-1]:
            start=i
            rep2 = rep[i:lr-1]
            break
    mod = len(rep2)
    modL = [i%mod for i in range(start,start+mod)]
    resM = k%mod
    for i in range(mod):
        if resM == modL[i]:
            print(rep2[i])

### FIXED CODE ###

n,k=map(int,input().split())
a = list(map(int,input().split()))
visit = []
visit = [0]*n
pos=0
move=[]
roop=[]
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos]+=1
    pos = a[pos]-1
if len(move)>k:
    print(move[k]+1)
else:
    mod = (k-(len(move)-len(roop)))%len(roop)
    print(roop[mod]+1)
### BUGGY CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
th = Counter(st[:n])["W"] + Counter(st[n+1:])["E"]
previous = st[0]
for i in range(1,n):
    temp = ma[-1]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
    if(th-(n-i) > min(ma)):
        break
print(min(ma))

### FIXED CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
previous = st[0]
for i in range(1,n):
    temp = ma[-1]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
print(sorted(ma)[0])
### BUGGY CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)
    
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    n,q=map(int,readline().split())
    stx = [[int(x) for x in readline().split()] for _ in range(n)]
    event=[]
    stop=set()
    for s,t,x in stx:
        event.append([s-x,1,x])
        event.append([t-x,-1,x])
    for i in range(q):
        event.append([int(input()),2,i])
    event.sort()
    
    ans=[0]*q
    
    stop=set()
    hq=[]
    for e in event:
        t,op,x=map(lambda x:x,e)
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)
    
        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)

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

    event=[]
    for _ in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()
### BUGGY CODE ###

import queue
n,m=map(int,input().split())
a=[[0 for i in range(n)] for j in range(n)]
for i in range(0,m):
    b,c=map(int,input().split())
    a[b-1][c-1]=1
    a[c-1][b-1]=1
re=[0 for i in range(n)]
le=[0]
for i in range(0,n):
    if re[i]==0:
        ans=queue.Queue()
        ans.put(i)
        le.append(1)
        while ans.empty()==False:
            d=ans.get()
            for j in range(n):
                if a[i][j]==1 and re[j]==0:
                    ans.put(j)
                    re[j]=1
                    le[-1]+=1
print(max(le))

### FIXED CODE ###

import queue
n,m=map(int,input().split())
a=[[] for j in range(n)]
for i in range(0,m):
    b,c=map(int,input().split())
    a[b-1].append(c-1)
    a[c-1].append(b-1)
re=[0 for i in range(n)]
le=[0]
for i in range(0,n):
    if re[i]==0:
        ans=queue.Queue()
        ans.put(i)
        le.append(1)
        re[i]=1
        while ans.empty()==False:
            d=ans.get()
            for j in range(len(a[d])):
                if re[a[d][j]]==0:
                    ans.put(a[d][j])
                    re[a[d][j]]=1
                    le[-1]+=1
print(max(le))
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, n):
    ans += i
print(ans)

### FIXED CODE ###

n = int(input())
if n%2 != 0:
    print(n*(n//2))
else:
    print(n*(n//2) - n//2)
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

for _ in range(M):
    b,c = [int(x) for x in input().split()]
    A.extend([c] * b)

A.sort(reverse=True)

ans = sum(A[:N])
print(ans)


### FIXED CODE ###

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort(reverse=True)

CB = []
for i in range(M):
    b, c = [int(x) for x in input().split()]
    CB.append((c, b))
CB.sort(reverse=True)


L = []
for cb in CB:
    if len(L) >= N:
        break
    L.extend([cb[0]] * cb[1])

newA = A + L
newA.sort(reverse=True)

newA = newA[0:N]
ans = sum(newA)

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

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

ans = 0

for i in range(N-1):
    count = 0
    for j in range(i, N):
        try:
            if H[j] < H[j+1]:
                break
            else:
                count += 1
        except IndexError:
            pass

    ans = max(ans, count)

print(ans)

### FIXED CODE ###

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

count = 0
ans = 0
a = 0

for i in H:
    a, b = i, a

    if a <= b:
        count += 1
    else:
        count = 0

    ans = max(ans, count)

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

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

while(True):
    if(N <= abs(N-K)):
        print(N)
        break
    else:
        N = abs(N-K)


### FIXED CODE ###

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

N = N%K
while(True):
    if(N <= abs(N-K)):
        print(N)
        break
    else:
        N = abs(N-K)
### BUGGY CODE ###

def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for m, lr in merge2(a,b):
    yield m

def merge2(a,b,lr=None):
  for i in range(1,len(b)):
    if lr!=0:
      m = comp(b[i:], a)
      if m:
        yield  b[:i]+m+a[len(b)-i:], 1
    if lr!=1:
      m = comp(b, a[-len(b)+i:])
      if m:
        yield a[:-len(b)+i]+m+b[-i:], 0
  yield a+b, 0
  yield b+a, 1

a=input()
b=input()
c=input()
a,b,c=sorted([a,b,c],key=len,reverse=True)

abc = float("inf")
for d in merge(a,b):
  if len(d) > abc:
    break
  l = len(next(merge(d, c)))
  abc = min(abc, l)

for d, lr in merge2(a,c):
  if len(d) > abc:
    break
  l = len(next(merge2(d, b, lr))[0])
  abc = min(abc, l)

print(abc)



### FIXED CODE ###

from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k]))

def _merge_mid(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge_mid(a,b):
  return list(_merge_mid(a,b))

def _merge_right(a,b):
  la, lb = map(len,[a,b])
  for i in range(max(la-lb+1, 1),la):
    if comp(b, a[i-la:]):
      yield i
  yield la

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

a=input()
b=input()
c=input()

print(min_merge(a,b,c))
### BUGGY CODE ###

X = int(input())

root = int(X**(1/5))

if root**5 < X:
    rest = X - root**5
    another = -int(rest**(1/5))
else:
    rest = root**5 - X
    another = int(rest**(1/5))

while root**5 - another**5 != X:
    another_plus = another + 1
    another_minus = another - 1
    if root**5 - another_plus**5 == X:
        another = another_plus
        break
    if root**5 - another_minus**5 == X:
        another = another_minus
        break


print(root, another)


### FIXED CODE ###

X = int(input())

import sys

for a in range(-118, 120):
    for b in range(-119, 119):
        if a**5 - b**5 == X:
            print(a, b)
            sys.exit()
### BUGGY CODE ###

N, Q = [int(x) for x in input().split()]
ab_list = [[int(x) for x in input().split()] for _ in range(N-1)]
tmp = [[int(x) for x in input().split()] for _ in range(Q)]
x_list = [0] * (N+1)
for p, x in tmp:
    x_list[p] += x
to = [[] for _ in range(N+1)]
for a, b in ab_list:
    to[b].append(a)
subtree = [[i] for i in range(N+1)]
for j in range(N, 0, -1):
    for u in to[j]:
        subtree[u].extend(subtree[j])
ans = [0] * N
for i, x in enumerate(x_list):
    for u in subtree[i]:
        ans[u-1] += x
print(' '.join([str(i) for i in ans]))


### FIXED CODE ###

N, Q = [int(x) for x in input().split()]
to = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = [int(x)-1 for x in input().split()]
    to[b].append(a)
    to[a].append(b)
ans = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    p -= 1
    ans[p] += x

from collections import deque
q = deque()
q.append(0)
visited = [0] * N

while(q):
    v = q.pop()
    visited[v] = 1    
    for u in to[v]:
        if visited[u] == 1: continue
        ans[u] += ans[v]
        q.append(u)
print(' '.join([str(i) for i in ans]))
### BUGGY CODE ###

n = int(input())
numlist = list(map(int, input().split(" ")))
ans = []

for i in range(1, n + 1):
    ans.append(numlist.count(i))

for i in numlist:
    ans[i - 1] -= 1
    sum = 0
    for j in ans:
        sum += int(j * (j - 1) / 2)
    print(sum)
    ans[i - 1] += 1


### FIXED CODE ###

n = int(input())
numlist = list(map(int, input().split(" ")))

import collections

numcount=collections.Counter(numlist)


sum = 0
for i in numcount.values():
    sum += int(i * (i - 1) / 2)

for i in numlist:
    print(sum - numcount[i] + 1)
### BUGGY CODE ###

from collections import Counter
n,m = map(int, input().split())

pen = 0
ac = 0
ques = []
ac_ques = set()

for _ in range(m):
    p,s = map(str, input().split())
    if p not in ac_ques:
        if s == "WA":
            ques.append(p)
        else:
            c = Counter(ques)
            pen += c[p]
            ac_ques.add(p)

print(len(ac_ques),pen)

### FIXED CODE ###

import numpy as np
n,m = map(int, input().split())

ac_ques = np.array([0]*n)
count = np.array([0]*n)

for _ in range(m):
    p,s = map(str, input().split())
    if ac_ques[int(p)-1] == 0:
        if s == "WA":
            count[int(p)-1] += 1
        else:
            ac_ques[int(p)-1] = 1

print(sum(ac_ques),sum(ac_ques * count))
### BUGGY CODE ###

def main():
  h,*s=open(0)
  h,w,k=map(int,h.split())
  s=[list(map(int,t[:w]))for t in s]
  m=9e9
  for i in range(1<<h-1):
    t=[]
    b=v=l=0
    for j in range(h):
      if i>>j&1:
        t+=s[b:j+1],
        b=j+1
        l+=1
    t+=s[b:],
    l+=1
    c=[0]*l
    for i in range(w):
      f=g=0
      u=[]
      for j in range(l):
        d=sum(t[i]for t in t[j])
        u+=d,
        if d>k:
          g=1
          break
        c[j]+=d
        f|=c[j]>k
      else:
        if f:
          c=u
          v+=1
      if g:break
    else:
      if v+l-1<m:m=v+l-1
  print(m)
main()

### FIXED CODE ###

h,*s=open(0)
h,w,k=map(int,h.split())
s=[list(map(int,t[:w]))for t in s]
m=9e9
for i in range(1<<h-1):
  t=[]
  b=v=l=0
  for j in range(h):
    if i>>j&1:
      t+=s[b:j+1],
      b=j+1
      l+=1
  t+=s[b:],
  l+=1
  c=[0]*l
  for i in range(w):
    f=g=0
    u=[]
    for j in range(l):
      d=sum(t[i]for t in t[j])
      u+=d,
      if d>k:
        g=1
        break
      c[j]+=d
      f|=c[j]>k
    else:
      v+=f
      if f:c=u
    if g:break
  else:m=min(m,v+l-1)
print(m)
### BUGGY CODE ###

n,m,s,t=map(int,input().split())
yen=[[]*n for i in range(n)]
sunuke=[[]*n for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u-1].append((a,v-1))
  yen[v-1].append((a,u-1))
  sunuke[u-1].append((b,v-1))
  sunuke[v-1].append((b,u-1))


#ダイクストラ法
#n:頂点数　s:始点　es:隣接リスト表現
import heapq
def dijkstra(n,s,es):
  d=[float("INF")]*n
  d[s]=0
  used=[False]*n
  used[s]=True
  edgelist=[]
  for to in es[s]:
    heapq.heappush(edgelist,to)
  while len(edgelist)>0:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    if used[v]:
      continue
    used[v]=True
    d[v]=minedge[0]
    for to in es[v]:
      heapq.heappush(edgelist,(d[v]+to[0],to[1]))
  return d

ans=[0]*n
d_yen=dijkstra(n,s-1,yen)
d_sunuke=dijkstra(n,t-1,sunuke)
for i in range(n):
  ans[i]=d_yen[i]+d_sunuke[i]

for j in range(n):
  print(10**15-min(ans[j:n]))
  
  
  
  
      
    
    
    
    
  
  


  

### FIXED CODE ###

n,m,s,t=map(int,input().split())
yen=[[]*(n+1) for i in range(n+1)]
sunuke=[[]*(n+1) for i in range(n+1)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u].append((a,v))
  yen[v].append((a,u))
  sunuke[u].append((b,v))
  sunuke[v].append((b,u))
  
import heapq
#n:頂点数、m:辺の数　s:始点　es:辺のリスト
def dijkstra(n,m,s,es):
  #used:訪問済みかどうかを確認する　false 使ってない
  used=[False]*(n+1)
  d=[float("INF")]*(n+1)
  d[s]=0
  used[s]=True
  q=[]
  for to in es[s]:
    heapq.heappush(q,to)
  while len(q)>0:
    minedge=heapq.heappop(q)
    v=minedge[1]
    if used[v]==True:
      continue
    cost=minedge[0]
    d[v]=cost
    used[v]=True
    for to in es[v]:
      heapq.heappush(q,(d[v]+to[0],to[1]))
  return d


d_yen=dijkstra(n,m,s,yen)
d_sunuke=dijkstra(n,m,t,sunuke)

ans=[float("INF")]*(n+1)
num=float("INF")
for i in range(n,0,-1):
  num=min(d_yen[i]+d_sunuke[i],num)
  ans[i]=num
  
for j in range(1,n+1):
  print(10**15-ans[j])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = map(int,input().split())
    graph[(p,0)].append((p,c))
    graph[(p,c)].append((p,0))
    graph[(q,0)].append((q,c))
    graph[(q,c)].append((q,0))
    graph[(p,c)].append((q,c))
    graph[(q,c)].append((p,c))

INF = 10 ** 9
dist = defaultdict(lambda: INF)

visited = set()
q = [(1,0)] # 0 が会社に属していない状態
dist[(1,0)] = 0
d = 0
while q:
    qq = []
    while q:
        v,c = q.pop()
        if c == 0:
            for v1,c1 in graph[(v,0)]:
                if dist[(v1,c1)] <= d + 1:
                    continue
                dist[(v1,c1)] = d + 1
                qq.append((v1,c1))
        else:
            for v1,c1 in graph[(v,c)]:
                if dist[(v1,c1)] <= d:
                    continue
                dist[(v1,c1)] = d
                q.append((v1,c1))
    d += 1
    q = qq

answer = dist[(N,0)]
if answer == INF:
    answer = -1
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = map(int,input().split())
    p <<= L
    q <<= L
    graph[p].append(p+c)
    graph[p+c].append(p)
    graph[q].append(q+c)
    graph[q+c].append(q)
    graph[p+c].append(q+c)
    graph[q+c].append(p+c)

INF = 10 ** 9
dist = defaultdict(lambda: INF)

start = 1 << L
goal = N << L

q = [start] # 0 が会社に属していない状態
dist[start] = 0
d = 0
while q:
    qq = []
    while q:
        x = q.pop()
        if x & mask == 0:
            for y in graph[x]:
                if dist[y] <= d + 1:
                    continue
                dist[y] = d + 1
                qq.append(y)
        else:
            for y in graph[x]:
                if dist[y] <= d:
                    continue
                dist[y] = d
                q.append(y)
    d += 1
    q = qq

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)