Harryxun/stf_run huggingface dataset:
# coding: utf-8
X,N=map(int,input().split())
P=[]
if N!=0:
    P=list(map(int,input().split()))
K=[]
for i in range(1,101):
    if not(i in P):
        K.append(i)

ans=[]

for i in range(len(K)):
    ans.append([abs(X-K[i]),K[i]])

ans.sort()

print(ans[0][1])


### FIXED CODE ###

# coding: utf-8
X,N=map(int,input().split())
P=[]
if N!=0:
    P=list(map(int,input().split()))
K=[]
for i in range(102):
    if not(i in P):
        K.append(i)

ans=[]

for i in range(len(K)):
    ans.append([abs(X-K[i]),K[i]])

ans.sort()

A=[]

for i in range(len(ans)):
    if ans[i][0]==ans[0][0]:
        A.append(ans[i][1])

print(min(A))
N = int(input())
d = [int(x) for x in input().split()]
t = 0
for i in itertools.permutations(d, N):
    t += i[0]*i[1]
print(total)

### FIXED CODE ###

N = int(input())
d = [int(x) for x in input().split()]
t = 0
for i in range(N-1):
    for j in range(i+1, N):
      t += d[i]*d[j]
print(t)
N=input()
a=[]
for i in range(2*N):
	x,y=map(int, raw_input().split())
	if i<N: a.append([x,y,"R"])
	else: a.append([x,y,"B"])

b=sorted(a, key=lambda x: x[0], reverse=True)


q=[]
ans=0
for i in b:
	x=i[1]
	type=i[2]
	if type=="B":
		q.append(x)
	elif type=="R" and len(q)>0:
		up=0
		tmp=[]
		for j in q:
			if x<=j:
				tmp.append(j)
				up=1
		else:
			ans+=up
		val=min(tmp)
		q.remove(val)

print ans

### FIXED CODE ###

N=input()
a=[]
for i in range(2*N):
	x,y=map(int, raw_input().split())
	if i<N: a.append([x,y,"R"])
	else: a.append([x,y,"B"])

b=sorted(a, key=lambda x: x[0], reverse=True)


q=[]
ans=0
for i in b:
	x=i[1]
	type=i[2]
	if type=="B":
		q.append(x)
	elif type=="R" and len(q)>0:
		up=0
		tmp=[]
		for j in q:
			if x<=j:
				tmp.append(j)
				up=1
		ans+=up
		if len(tmp)>0:
			val=min(tmp)
			q.remove(val)

print ans
a=int(input())
b=int(input())
result=[a*b,a*(a+b)]
print(result)

### FIXED CODE ###

a,b=list(map(int,input().split()))
print(a*b,2*(a+b))
n, m= map(int, input().split())

p_y_li = [list(map(int, (input() + " {}".format(i)).split())) for i in range(m)]

p_y_li.sort(key = lambda x : x[1])

li = [0 for _ in range(m)]
for i in range(m):
    ans = ""
    p = p_y_li[i][0]
    li[p-1] += 1
    x = li[p-1]
    ans = str(p).zfill(6) + str(x).zfill(6)
    p_y_li[i].append(ans)

p_y_li.sort(key = lambda x : x[2])
for i in p_y_li:
    print(i[3])

### FIXED CODE ###

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

p_y_li = [list(map(int, (input() + " {}".format(i)).split())) for i in range(m)]

p_y_li.sort(key = lambda x : x[1])

li = [0 for _ in range(n)]
for i in range(m):
    ans = ""
    p = p_y_li[i][0]
    li[p-1] += 1
    x = li[p-1]
    ans = str(p).zfill(6) + str(x).zfill(6)
    p_y_li[i].append(ans)

p_y_li.sort(key = lambda x : x[2])
for i in p_y_li:
    print(i[3])
Q = 6 - A -B
print(Q)

### FIXED CODE ###

A = int(input())
B = int(input())
Q = 6-A-B

print(Q)
n = int(input())
M = 0
for i in range(1, n + 1):
  t = i
  s = 0
  while t % 2 == 0:
    t /= 2
    s += 1
  if M < s:
    M = s
    ans = i
print(ans)

### FIXED CODE ###

n = int(input())
M = 0
ans = 1
for i in range(1, n + 1):
  t = i
  s = 0
  while t % 2 == 0:
    t /= 2
    s += 1
  if M < s:
    M = s
    ans = i
print(ans)
N=int(input())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))

ablist=[]
for i in range(N):
  ablist.append(alist[i]-blist[i])
  
ablist.sort()
#print(ablist)

if ablist[0] >= 0:
  print("0")
elif sum(ablist) < 0:
  print("-1")
else:
  cnt = 0
  sum_ab = 0
  for ab in ablist:
    if ab<0:
      cnt += 1
      sum_ab += ab
    else:
      break
      
  for ab in reversed(ablist):
    cnt += 1
    sum_ab += ab
    if sum_ab >= 0:
      break
      
print(cnt)

### FIXED CODE ###

N=int(input())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))

ablist=[]
for i in range(N):
  ablist.append(alist[i]-blist[i])
  
ablist.sort()
#print(ablist)

if ablist[0] >= 0:
  print("0")
elif sum(ablist) < 0:
  print("-1")
else:
  cnt = 0
  sum_ab = 0
  for ab in ablist:
    if ab<0:
      cnt += 1
      sum_ab += ab
    else:
      break
      
  for ab in reversed(ablist):
    cnt += 1
    sum_ab += ab
    if sum_ab >= 0:
      break
      
  print(cnt)
from numpy import int_, eye

mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())
A = int_(A).reshape(N, N)

ans = eye(N, dtype=int_)
while K:
    if K & 1:
        ans = (ans.dot(A)) % mod
    A = A.dot(A) % mod
    K //= 2

print(ans.sum() % mod)

### FIXED CODE ###

from numpy import array, eye

mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())
A = array(A, dtype=object).reshape(N, N)

ans = eye(N, dtype=object)
while K:
    if K & 1:
        ans = (ans.dot(A)) % mod
    A = A.dot(A) % mod
    K //= 2

print(ans.sum() % mod)
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    # 全部0の最遅ケースでもlog(N)*2くらいで収束する log(2*10**5)<50
    for _ in range(min(K, 50)):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            A[i] = tmp[i] + b[i]
        # print(A)

    print(*A)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    # 全部0の最遅ケースでもlog(N)*2くらいで収束する log(2*10**5)<50
    for _ in range(min(K, 50)):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            b[i+1] = tmp[i] + b[i]
        for i in range(N):
            A[i] = b[i+1] 
        # print(A)

    print(*A)

if __name__ == '__main__':
    resolve()
list_1 = [int(x) for x in il_1.split(' ')] # N と　X
list_2 = [int(x) for x in il_2.split(' ')]
 
sum_list = []
for i in list_2:
    if sum(sum_list) < list_1[1]:
      sum_list.append(i)
    elif sum(sum_list) == list_1[1]:
      print(len(sum_list) + 1)
      break
    elif sum(sum_list) > list_1[1]:
      print(len(sum_list))
      break
if sum(sum_list) < list_1[1]
    print(list_1[0] + 1)


### FIXED CODE ###

input_line = input()
l = input_line.split(' ')
l = [int(x) for x in l]

if l[0] < l[1]:
    print(0)
else:
    print(10)
a,b,c = map(int,input().split())
n = 0
for i in range(min(a,b)):
  if a%i == 0 and b%i == 0:
    n += 1
    if n ==c:
      print(i)
      break
    else:
      pass

### FIXED CODE ###

import fractions
a,b,K = map(int,input().split())
g = fractions.gcd(a,b)
cnt = 0
ans = 0
for i in range(g,0,-1):
    if g % i == 0:
        cnt += 1
        if cnt == K:
            ans = i
            break
    else:
        pass
print(ans)
A, B, C, K = int(input().split())
if K<=A:
    print(K)
elif A<K<=A+B:
    print(A)
else:
    print(A-(K-A-B))

### FIXED CODE ###

A, B, C, K = map(int, input().split())
if K<=A:
    print(K)
elif A<K<=A+B:
    print(A)
else:
    print(A-(K-A-B))
from functool import lru_cache
N = int(input())
A = list(map(int, input().split()))
INF = 1.0e+100

@lru_cache(maxsize=None)
def f(l, r):
  if r - l == 1:
    return (A[l], 0)
  ret = (INF, INF)
  for i in range(l+1, r):
    (lr, lc) = f(l, i)
    (rr, rc) = f(i, r)
    if lr+rr+lc+rc < ret[1]:
      ret = (lr+rr, lr+rr+lc+rc)
  return ret

print(f(0, N)[1])


### FIXED CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

INF = 1.0e+100


dp = [[[None, INF] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N):
    dp[i][i+1] = [A[i], 0]

for g in range(2, N+1):
    for l in range(N-g+1):
        r = l + g
        for i in range(l+1, r):
            lv, lc = dp[l][i]
            rv, rc = dp[i][r]
            nc = lv + rv + lc + rc
            if dp[l][r][1] > nc:
                dp[l][r][0] = lv + rv
                dp[l][r][1] = nc

print(dp[0][N][1])
N,M=map(int, input().split())
A=[list(map(int, input().split()))  for _ in range(M)]
A = sorted(A, reverse=False, key=lambda x: x[0])

ans=[[] for i in range(N)]
if A[0][0]==1 and A[0][1]==0:
    print(-1)
    exit(0)

elif A[0][0]==1:
    ans[0]=A[0][1]
elif A[0][0]!=1:
    ans[0]=1
    pt=1
    while pt+1<A[0][0]:
        ans[pt]=0
        pt+=1
    ans[pt]=A[0][1]
    pt+=1

for i in range(1,M):
    while pt+1<A[i][0]:
        ans[pt]=0
        pt+=1
    if A[i-1][0]==A[i][0] and A[i-1][1]!=A[i][1]:
        print(-1)
        exit(0)
    else: ans[pt]=A[i][1]
        
print(''.join(map(str,ans))) 

### FIXED CODE ###

N,M=map(int, input().split())
A=[list(map(int, input().split()))  for _ in range(M)]
A = sorted(A, reverse=False, key=lambda x: x[0])

if M==0:
    if N==3:
        print(100)
        exit(0)
    elif N==2:
        print(10)
        exit(0)        
    elif N==1:
        print(0)
        exit(0)

if N!=1 and A[0][0]==1 and A[0][1]==0:
    print(-1)
    exit(0)
i=1
j=len(A)
while i<j:
    if A[i][0]==A[i-1][0] and A[i][1]==A[i-1][1]:
        A.pop(i)
        j-=1
        continue
    elif A[i][0]==A[i-1][0] and A[i][1]!=A[i-1][1]:
        print(-1)
        exit(0)
    i+=1
ans=[None]*N

for i,j in A:
    ans[i-1]=j

for i in range(len(ans)):
    if ans[i]==None:
        if i==0:
            ans[i]=1
        else:
            ans[i]=0

print(''.join(map(str,ans)))
n=input()
s=0
for i in n:
  s+=int(i)
if s%9==0:
  print(Yes)
else:
  print("No")
  

### FIXED CODE ###

n=input()
s=0
for i in n:
  s+=int(i)
  s=s%9
if s%9==0:
  print("Yes")
else:
  print("No")
n,m = map(int, input().split())
a = list(map(int, input().split()))

s = a.sum()
min_num = s//(4*m)

res = "No"
count = 0
for x in a:
    if x >= min_num:
        count += 1
    if count >= m:
        res = "Yes"
        break
print(res)

### FIXED CODE ###

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

s = sum(a)
min_num = float(s)/(4*m)

res = "No"
count = 0
for x in a:
    if x >= min_num:
        count += 1
    if count >= m:
        res = "Yes"
        break
print(res)
a, b, c = map(int, input().split())
if a + b + 1 >= c:
    c = b + c
    
elif a + b < c:
    c = a + b  + 1 + b
input(c)    
  

### FIXED CODE ###

a, b, c = map(int, input().split())
if c <= a+b:
    print(b+c)
else:
    print(2*b+a+1)
N=int(input())
print(X//3)

### FIXED CODE ###

N=int(input())
print(N//3)
from collections import deque

def dfs(xs):
    x = xs.popleft()

    if len(xs) == 0:
        return x

    # not +
    xs2 = xs.copy()
    y   = xs2.popleft()
    xy  = int(str(x)+str(y))
    xs2.appendleft(xy)
    b = dfs(xs2)

    # has +
    a = x * 2 + dfs(xs)


    return a+b


s  = str(input())
xs = list(map(int,s))
xs = deque(xs)

print(dfs(xs))

### FIXED CODE ###

import sys
import copy
from collections import deque

sys.setrecursionlimit(1000000000)

def dfs(xs,q):
    if len(xs) == 0:
        return sum(int(i) for i in q)

    x = xs.popleft()

    if len(q) == 0:
        q.append(x)
        return dfs(xs,q)


    a1 = copy.copy(xs)
    a2 = copy.copy(xs)

    q1 = copy.copy(q)
    q2 = copy.copy(q)

    q1.append(x)

    y  = q2.pop()
    yx = y + x
    q2.append(yx)

    return dfs(a1,q1) + dfs(a2,q2)


s  = str(input())
xs = deque(list(s))

print(dfs(xs,deque([])))
N=int(input())
if N==0:
    a=0
elif N>0:
    a=0
    i=31
    while i>=0:
        if N%(2**i)==0:
            if i%2==1:
                a+=2**(i+1)+2**i
                break
            else:
                a+=2**i
                break
        else:
            if N>2**i:
                N-=2**i
                if i%2==1:
                    a+=2**(i+1)+2**i
                else:
                    a+=2**i
            i-=1
else:
    a=0
    i=31
    while i>=0:
        if N%(2**i)==0:
            if i%2!=1:
                a+=2**(i+1)+2**i
                break
            else:
                a+=2**i
                break
        else:
            if -N>2**i:
                N+=2**i
                if i%2!=1:
                    a+=2**(i+1)+2**i
                else:
                    a+=2**i
            i-=1
print(int(format(a,"b"))


### FIXED CODE ###

N=int(input())
if N==0:
    N=0
elif N>0:
    n=format(N,"b")
    for i in range(10**9):
        if i==len(n):
            break
        elif i%2==1:
            if n[-i-1]=="1":
                N+=2**(i+1)
                n=format(N,"b")
else:
    N*=-1
    n=format(N,"b")
    for i in range(10**9):
        if i==len(n):
            break
        elif i%2==0:
            if n[-i-1]=="1":
                N+=2**(i+1)
                n=format(N,"b")
print(int(format(N,"b")))
import itertools


input()
s = list(input())
r =[]
g =[]
b =[]
n= len(s)
ans =0
for i in range(n):
    if s[i]== "R":
        r.append(i+1)
    elif s[i]== "G":
        g.append(i+1)
    else:
        b.append(i+1)

for ri , gi in itertools.product(r,g):
    rg=gi-a
    if rg+gi in b:
        ans -=1
    if  ri-rg in b:
        ans -=1
    if (gi+ri)/2 in b:
        ans -=1

ans += len(r)*len(b)*len(g)
print(ans)

### FIXED CODE ###

import sys
import math
import itertools
from functools import reduce
from functools import lru_cache


# \n
def input():
    return sys.stdin.readline().rstrip()

def main():

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

    R=[0]*N
    G=[0]*N
    B=[0]*N
    r=0
    g  =0
    b=0
    count =0
    for i in range(N-1,-1,-1):
        if S[i] =="R":
            r+=1
        elif S[i] =="G":
            g+=1
        else:
            b+=1
        R[i]=r
        G[i]=g
        B[i]=b

    count =0
    for i in range(N):



        for j in range(i+1,N):
            SE = set(["R", "G", "B"])
            I = S[i]
            SE.remove(I)
            J =S[j]
            if I==J:
                continue
            SE.remove(J)
            if "G" in SE:
                count+=G[j]
                if j+j-i <N and S[j+j-i] =="G":
                    count -=1

            elif "R" in SE:
                count+=R[j]
                if j+j-i <N and S[j+j-i] =="R":
                    count -=1
            else:
                count+=B[j]
                if j+j-i <N and S[j+j-i] =="B":
                    count -=1



    print(count)


if __name__ == "__main__":
    main()
n = int(input())
a = list(map(int, input().split()))
if a[0] != 0:
  print(0)
else:
  print(a[n+4])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
L = [0 for _ in range(n)]
L[0] = a[0]
for i in range(1, n):
  L[i] = L[i-1] + a[i]
delay = 0
all_over = 0
anti_delay = 0
anti_all_over = 0
if a[0] != 0:
  antiL = L[:]
  sign = (a[0] > 0) - (a[0] < 0)
  for i in range(1, n):
    L[i] += delay
    if L[i] <= 0 and sign == -1:
      delay += 1 - L[i]
      all_over += 1 - L[i]
      L[i] = 1
    elif L[i] >= 0 and sign == 1:
      delay -= L[i] + 1
      all_over += L[i] + 1
      L[i] = -1
    sign *= -1
  if antiL[0] < 0:
    sign = 1
    anti_delay = 1 - antiL[0]
    anti_all_over = 1 - antiL[0]
  else:
    sign = -1
    anti_delay = -(antiL[0] + 1)
    anti_all_over = antiL[0] + 1
  for i in range(1, n):
    antiL[i] += anti_delay
    if antiL[i] <= 0 and sign == -1:
      anti_delay += 1 - antiL[i]
      anti_all_over += 1 - antiL[i]
      antiL[i] = 1
    elif antiL[i] >= 0 and sign == 1:
      anti_delay -= antiL[i] + 1
      anti_all_over += antiL[i] + 1
      antiL[i] = -1
    sign *= -1
  print(min(anti_all_over, all_over))
else:
  posL = L[:]
  negL = L[:]
  pos_delay, neg_delay = 1, -1
  pos_all_over, neg_all_over = 1, 1
  sign = 1
  for i in range(1, n):
    posL[i] += pos_delay
    if posL[i] <= 0 and sign == -1:
      pos_delay += 1 - posL[i]
      pos_all_over += 1 - posL[i]
      posL[i] = 1
    elif posL[i] >= 0 and sign == 1:
      pos_delay -= posL[i] + 1
      pos_all_over += posL[i] + 1
      posL[i] = -1
    sign *= -1
  sign = -1
  for i in range(1, n):
    negL[i] += neg_delay
    if negL[i] <= 0 and sign == -1:
      neg_delay += 1 - negL[i]
      neg_all_over += 1 - negL[i]
      negL[i] = 1
    elif negL[i] >= 0 and sign == 1:
      neg_delay -= negL[i] + 1
      neg_all_over += negL[i] + 1
      negL[i] = -1
    sign *= -1
  print(min(pos_all_over, neg_all_over))
I=input()

if I == "A":
  print("T")
elif I = "T":
  print("A")
elif I == "C":
  print("G")
else:
  print("C")

### FIXED CODE ###

I=input()

if I == "A":
  print("T")
elif I == "T":
  print("A")
elif I == "C":
  print("G")
else:
  print("C")
def start():
    n = int(input())
    arr = [int(v) for v in input().split(" ")]
    dp = [-1] * 100005
    def frog_1(i):
        if i == n - 1:
            return 0
        if i >= n:
            return float("inf")
        if dp[i] != -1:
            return dp[i]
        left = abs(arr[i] - arr[i + 1]) + frog_1(i + 1)
        right = float("inf")
        if i+2 < n:
            right = abs(arr[i] - arr[i + 2]) + frog_1(i + 2)
        dp[i] = min(left, right)
        return min(left, right)
    print(frog_1(0), end="")

start()


### FIXED CODE ###

import sys

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

dp = [sys.maxsize] * n
dp[0] = 0
for i in range(n):
    for j in (i + 1, i + 2):
        if j < n:
            dp[j] = min(dp[j], dp[i] + abs(a[i] - a[j]))
print(dp[n - 1], end="")
s = input()

checker = ''

if len(s) == 2:
    if s[0] == s[1]:
        print(1, 2)
        checker += '*'
    else:
        print(-1, -1)
        checker += '*'


if checker == '':
    for a, b in zip(range(len(s)-1), range(1,len(s))):
        if s[a] == s[b]:
            print(a+1, b+1)
            checker += '*'
            break

if checker == '':
    for a, c in zip(range(len(s)-2), range(2, len(s))):
        if s[a] == s[c]:
            print(a+1, c+1)
            chekcher += '*'
            break

if checker == '':
    print(-1, -1)


### FIXED CODE ###

s = input()

checker = ''

if len(s) == 2:
    if s[0] == s[1]:
        print(1, 2)
        checker += '*'
    else:
        print(-1, -1)
        checker += '*'


if checker == '':
    for a, b in zip(range(len(s)-1), range(1,len(s))):
        if s[a] == s[b]:
            print(a+1, b+1)
            checker += '*'
            break

if checker == '':
    for a, c in zip(range(len(s)-2), range(2, len(s))):
        if s[a] == s[c]:
            print(a+1, c+1)
            checker += '*'
            break

if checker == '':
    print(-1, -1)
import sys, os

f = lambda:list(map(int,input().split()))
a = ["dream", "dreamer", "erase", "eraser"]
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

t = input().strip()


def dfs(somes):
    if somes == t:
        return True
    
    if len(somes) >= len(t):
        return False

    for i in a:
        if i == t[len(somes):len(somes) + len(i)]:
            if dfs(somes+i):
                return True
    
    return False

def solve():
    s = ""
    if dfs(s):
        print("YES")
    else:
        print("NO")

solve()


### FIXED CODE ###

import sys, os

f = lambda:list(map(int,input().split()))
a = ["dream", "dreamer", "erase", "eraser"]
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

t = input().strip()
t = t[::-1]

def solve():
    s = ""
    for i in range(len(a)):
        a[i] = a[i][::-1]


    end = 0
    lent = len(t)
    while(len(s)<len(t)):
        ok = False
        for i in a:
            if len(s) + len(i) <= lent and i == t[len(s): len(s) + len(i)]:
                s += i
                ok = True

        if ok == False:
            print("NO")
            return
    
    print("YES")

solve()
import numpy as np
a,b,c,d=map(int,input().split())
n=np.array([c-a,d-b])
p=np.array([-n[1],n[0]])
print(*([c,d]+p),*([a,b]+p))

### FIXED CODE ###

import numpy as np
a,b,c,d=map(int,input().split())
n=np.array([c-a,d-b])
p=np.array([-n[1],n[0]])
print(*([c,d]+p), end=" ") #print(*([c,d]+p),*([a,b]+p))がPython3.4.3には対応してない？
print(*([a,b]+p))
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, m = map(int, input().split())
G = defaultdict(set)
seen = set()
for _ in range(n):
  p, q, c = map(int, input().split())
  G[(p, c)].add(((q, c), 0))
  G[(q, c)].add(((p, c), 0))
  G[(p, c)].add(((p, -1), 0))
  G[(q, c)].add(((q, -1), 0))
  G[(p, -1)].add(((p, c), 1))
  G[(q, -1)].add(((q, c), 1))
que = deque()
que.append(((1, -1), 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == (n, -1):
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)

### FIXED CODE ###

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

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)
n=int(input())
a=list(map(int,input().split()))

def f(x):
  x.sort()
  if x[0]==0:
    return 0

  x.sort(reversed=True)
  
  ans=1
  
  for i in a:
    ans=ans*i

    if ans>10**18:
      return -1
      
    if n==0:
      return ans
  


print(f(a))

### FIXED CODE ###

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

def f(x):
  x.sort()
  if x[0]==0:
    return 0

  x.sort(reverse=True)
  
  ans=1
  
  for i in a:
    ans=ans*i

    if ans>10**18:
      return -1
      
  return ans
  


print(f(a))
import itertools
N = int(input())
A = list(map(int, input().split()))

count = 0
for x in itertools.combinations(A, 3):
  if(x[0] + x[1] > x[2] and x[1] + x[2] > x[0] and x[2] + x[0] >x[1]):
    if(x[0]!=x[1] and x[0]!=x[1] and x[2] != x[3]):
    	count +=1
print(count)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if l[i] != l[j] != l[k]:
                if l[i] + l[j] > l[k]:
                    ans += 1
print(ans)
r, c = [int(i) for i in input().split()]

data = []
sum_row = [0] * (c + 1)

for ri in range(r):
    data.append([int(i) for i in input().split()])
    data[ri].append(sum(data[ri]))
    print(" ".join([str(d) for d in data[ri]]))
    for ci in range(c + 1):
        sum_row[ci] += data[ri][ci]

print(" ".join([str(s) for d in sum_row]))

### FIXED CODE ###

r, c = [int(i) for i in input().split()]

data = []
sum_row = [0] * (c + 1)

for ri in range(r):
    data.append([int(i) for i in input().split()])
    data[ri].append(sum(data[ri]))
    print(" ".join([str(d) for d in data[ri]]))
    for ci in range(c + 1):
        sum_row[ci] += data[ri][ci]

print(" ".join([str(s) for s in sum_row]))