Harryxun/stf_run huggingface dataset:
p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
cnt = 1
cnt0 =0
C = {0:0}
B = []
for i in range(N):
    a = A[i]
    if a==0:
        cnt = (cnt*(3-cnt0))%p
        cnt0 += 1
    else:
        cnt = (cnt*C[a-1])%p
        C[a-1] -= 1
    if a not in C:
        C[a] = 0
    C[a] += 1
print(cnt)

### FIXED CODE ###

p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
cnt = 1
cnt0 =0
C = {i:0 for i in range(N)}
B = []
for i in range(N):
    a = A[i]
    if a==0:
        cnt = (cnt*(3-cnt0))%p
        cnt0 += 1
    else:
        cnt = (cnt*C[a-1])%p
        C[a-1] -= 1
    C[a] += 1
print(cnt)
import cmath
import math

N = int(input())
pc = []
for i in range(N):
  x, y = map(int, input().split())
  c = x + y*1j
  p = cmath.phase(c)
  pc.append([p, c])
pc = sorted(pc)

ps = [pc[i][0] for i in range(N)]
cs = [pc[i][1] for i in range(N)]

def L(i, j, N):
  if i<j:
    return list(range(i, j))
  else:
    return list(range(0, i)) + list(range(j+1, N))

s = 0
m = 0

for i in range(N):
  for j in range(N):
    s = 0
    s = 0
    for k in L(i,j,N):
      s += cs[k]
    m = max(m, abs(s))

print(m)

### FIXED CODE ###

import cmath
import math

N = int(input())
pc = []
for i in range(N):
  x, y = map(int, input().split())
  c = x + y*1j
  p = cmath.phase(c)
  pc.append([p, c])
pc = sorted(pc, key=lambda x: x[0])

ps = [pc[i][0] for i in range(N)]
cs = [pc[i][1] for i in range(N)]

def L(i, j, N):
  if i<j:
    return list(range(i, j))
  else:
    return list(range(0, j)) + list(range(i+1, N))

s = 0
m = 0

for start in range(N):
  for end in range(N):
    s = 0
    #print(start,end,N,L(start,end,N))
    for k in L(start,end,N):
      s += cs[k]
    m = max(m, abs(s))
s = 0
for k in range(N):
  s += cs[k]
  m = max(m, abs(s))
print(m)
import sys

x = int(sys.argv[1])
a = int(sys.argv[2])
b = int(sys.argv[3])

if abs(x % a) > abs(x % b):
    print 'A'
else:
    print 'B'

### FIXED CODE ###

import sys

a = map(int,raw_input().strip().split(" "))

if abs(a[0] - a[1]) < abs(a[0] - a[2]):
    print 'A'
else:
    print 'B'
#code
a,b=map(int,input().split())
c,d=map(int,input().spit())
if a==c:
    print(0)
else:
    print(1)

### FIXED CODE ###

#code
a,b=map(int,input().split())
c,d=map(int,input().split())
if a==c:
    print(0)
else:
    print(1)
while 1:
        h,w=map(int,input().split())
        if h==w==0:
                break
        p=[[0 for i in range(w)] for j in range(h)]
        for i in range(w):
                for j in range(h):
                        if (i+j)%2=1:
                                p[i][j]=1
        for i in range(w):
                for j in range(h):              
                        if f[i][j]==1:
                                print('#',end='')
                        else :
                                print('.',end='')



### FIXED CODE ###

while 1:
     (H,W) = [int(i) for i in input().split()]
     if H==W==0:
          break
     for i in range(H):
          for j in range(W):
               if (i+j)%2==0:print ('#',end="")
               else: print('.',end="")
          print('')
     print('')
n = int(input())
str_list = input().split()

result = 1

for i in range(n):
  result = result * int(str_list[i])
  
t = 1
for j in range(18)
  t = t * 10
if(result > t):
  print('-1')
else:
  print(result)
   


### FIXED CODE ###

n = int(input())
str_list = input().split()

list = [int(k) for k in str_list]

list.sort(reverse=True)

result = 1

if(0 in list):
  print('0')
  exit()

for i in range(n):
  result = result * list[i]
  if(result > 1000000000000000000):
    print('-1')
    exit()

print(result)
###
#main
if __name__ == "__main__":
    N = int(input())
    S = input()
    count = 0
    for t in S:
        if t == "#":
            keepColor = True
        if keepColor and t == ".":
            count += 1
    count2 = 0
    keepColor = False
    for t in S[::-1]:
        if t == ".":
            keepColor = True
        if keepColor and t == "#":
            count2 += 1
    print(min(count,count2))
    

### FIXED CODE ###

###
#main
if __name__ == "__main__":
    N = int(input())
    S = input()
#    count = 0
    countMin = 200001
    counttemp = 0
    isWhite = True
    numlist = []
    for t in S:
        if t == "#" and isWhite:
            isWhite = False
            numlist.append(counttemp)
            counttemp = 0
        if t == "." and not isWhite:
            isWhite = True
            numlist.append(counttemp)
            counttemp = 0
        counttemp += 1
    
    numlist.append(counttemp)
    if len(numlist) <= 2:
        countMin = 0
    else:
        countMin = sum(numlist[2::2])
        temp = countMin
        i = 2
        while i < len(numlist):
            temp += numlist[i-1] - numlist[i]
            countMin = temp if temp < countMin else countMin
            i += 2
#    print(numlist)           
    print(countMin)
n,k,s=map(int,input().split())
a=list()
b=[2]*(n-k)+[1]*k
while len(a)<n:
    k-=1
    a+=[1]*(s-1)+[s]
a+=[s]*k
if s!=1:
    print(*a[len(a)-n:])
else:
    print(*b)

### FIXED CODE ###

n,k,s=map(int,input().split())
a=[s]*k
b=[3]*(n-k)+[s]*k
p=max(s//2-1,1)
for i in range(n-k):
    if i%p==0:
        a.append(s-1)
    else:
        a.append(2)
if s!=2 and s!=1:
    print(*a)
else:
    print(*b)
from collections import deque

N = int(input())
data1 = []
data2 = [[] for i in range(N)]
data3 = [set() for i in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    data1.append([a,b])
    data2[a].append(b)
    data2[b].append(a)

for i in range(N-1):
    a,b = data1[i]
    for x in data2[a]:
        for y in data2[b]:
            if y != a and x != b:
                data3[x].add(y)
                data3[y].add(x)

for i in range(N):
    data3[i] = list(data3[i])

#####print(data3)

s = [0,0,0]
while len(data2[s[0]]) <= 1:
    s[0] += 1

s[1] = data2[s[0]][0]
s[2] = data2[s[0]][1]

stack = deque([[s[0],1],[s[1],1],[s[2],2]])
ans = [0] * N
ans[s[0]] = 1
ans[s[1]] = 4
ans[s[2]] = 2
count = [3,7,5]

det = 0
while stack:
    p = stack.pop()
    for q in data3[p[0]]:
        if ans[q] != 0:
            continue
        if count[2] <= N and p[1]%3 != 2:
            ans[q] = count[2]
            count[2] += 3
            stack.append([q,2])
        elif count[1] <= N and p[1]%3 != 1:
            ans[q] = count[1]
            count[1] += 3
            stack.append([q,1])
        else:
            if count[0] > N:
                det = -1
            ans[q] = count[0]
            count[0] += 3
            stack.append([q,0])
        #####print(ans,stack)

if det == -1:
    print(-1)
else:
    print(" ".join(map(str,ans)))


### FIXED CODE ###

N = int(input())
data = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    data[a].append(b)
    data[b].append(a)

stack = [0]
d = [-1] * N
d[0] = 0

while stack:
    x = stack.pop()
    for y in data[x]:
        if d[y] != -1:
            continue
        d[y] = d[x] + 1
        stack.append(y)

mod = [[],[]]
for i in range(N):
    mod[d[i]%2].append(i)

ans = [0]*N

p = 1
q = 2
r = 3
if len(mod[0]) > N//3 and len(mod[1]) > N//3:
    for k in mod[0]:
        if p <= N:
            ans[k] = p
            p += 3
        else:
            ans[k] = r
            r += 3
    for l in mod[1]:
        if q <= N:
            ans[l] = q
            q += 3
        else:
            ans[l] = r
            r += 3
    
elif len(mod[0]) > N//3:
    for k in mod[0]:
        if p <= N:
            ans[k] = p
            p += 3
        elif q <= N:
            ans[k] = q
            q += 3
        else:
            ans[k] = r
            r += 3
    for l in mod[1]:
        ans[l] = r
        r += 3

else:
    for k in mod[1]:
        if p <= N:
            ans[k] = p
            p += 3
        elif q <= N:
            ans[k] = q
            q += 3
        else:
            ans[k] = r
            r += 3
    for l in mod[0]:
        ans[l] = r
        r += 3

print(" ".join(map(str,ans)))
import queue

def solve(w, h):
    q = queue.Queue()
    m = [['#' for i in range(w+2)] for j in range(h+2)]
    for i in range(h):
        inp = input()
        for j in range(w):
            m[i+1][j+1] = inp[j]
            if m[i+1][j+1] == '@':
                start = [i+1,j+1]
    q.put(start)
    c = 1
    while not q.empty():
        cur = q.get()
        XY = [(1,0), (-1, 0), (0, 1), (0, -1)]
        for x, y in XY:
            cx = cur[0]+x
            cy = cur[1]+y
            if m[cx][cy] == '.':
                m[cx][cy] = '#'
                q.put([cx, cy])
                c+=1
    return c

while True:
    w, h = [int(i) for i in input().split()]
    if w == 0 and h == 0:
        break
    print solve(w,h)

### FIXED CODE ###

import queue

def solve(w, h):
    q = queue.Queue()
    m = [['#' for i in range(w+2)] for j in range(h+2)]
    for i in range(h):
        inp = input()
        for j in range(w):
            m[i+1][j+1] = inp[j]
            if m[i+1][j+1] == '@':
                start = [i+1,j+1]
    q.put(start)
    c = 1
    while not q.empty():
        cur = q.get()
        XY = [(1,0), (-1, 0), (0, 1), (0, -1)]
        for x, y in XY:
            cx = cur[0]+x
            cy = cur[1]+y
            if m[cx][cy] == '.':
                m[cx][cy] = '#'
                q.put([cx, cy])
                c+=1
    return c

while True:
    w, h = [int(i) for i in input().split()]
    if w == 0 and h == 0:
        break
    print(solve(w,h))
a,d,x = map(int,input().split())

for i in range(10):
  s = r*x-d
  print(s)
  x = s
  

### FIXED CODE ###

r,d,x = map(int,input().split())

for i in range(10):
  s = r*x-d
  print(s)
  x = s
N, K = list(map(int, input().split()))

Alist = [int(i) for i in input().split(' ')]
import math

#print(Alist)
my_list = [9,8,7,4,7,1,3]

Alist=sorted(Alist, reverse=True)
#print(sorted(Alist, reverse=True))


for i in range(K):
   Alist[0]=Alist[0]/2
   if N>1: 
      if Alist[0]<Alist[1]:
         temp=Alist[0]
         Alist[0]=Alist[1]
         Alist[1]=temp
      if Alist[0]<Alist[i]:
         temp=Alist[0]
         Alist[0]=Alist[i]
         Alist[i]=temp
sum=0
#print(Alist)
for i in Alist:
   sum+=math.floor(i) 
print(int(sum))

### FIXED CODE ###

from heapq import heappush, heappop
import math
 
N,M = [int(i) for i in input().split(' ')]
inputList = [int(i) for i in input().split(' ')]
list = []
 
for i in inputList:
    heappush(list, -i)
 
for _ in range(M):
    heappush(list, math.ceil(heappop(list)/2))
    
print(-sum(list))
N=int(input())
s=[input() i for in range(N)]
for v in ['AC', 'WA', 'TLE','RE']:
  print('{0}x{1}'.format(v,s.count(v)))

### FIXED CODE ###

N=int(input())
s=[input()  for i in range(N)]
for v in ['AC', 'WA', 'TLE','RE']:
  print('{0} x {1}'.format(v,s.count(v)))
import sys

mod = int(1e9+7)

def dfs(i,dp,bad):
  	if i == 0:
      return 1
    if i in dp:
      return dp[i]
	dp[i] = 0;
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x)
        dp[i] %= mod
	return dp[i]
  
n = int(sys.stdin.next())
m = int(sys.stdin.next())
bad = set()
for _ in range(m):
  a = int(sys.stdin.next())
  bas.add(a)
print(dfs(n,dict(),bad))


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

mod = int(1e9+7)

def dfs(i,dp,bad):
    if i == 0:
      return 1
    if i in dp:
      return dp[i]
    dp[i] = 0
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x,dp,bad)
        dp[i] %= mod
    return dp[i]

n,m = [int(a) for a in input().split()]
bad = set()
for _ in range(m):
  a = int(input())
  bad.add(a)
print(dfs(n,dict(),bad))
N = int(input())
tako = []
ans = 0
for i in N:
  tako.append(int(input()))
for j in range(len(tako)-1):
  ans += tako[j]*tako[j+1]
ans += tako[1] * tako[-1]
print(ans)
  

### FIXED CODE ###

N = int(input())
ans = 0
tako = list(map(int, input().split()))
for j in range(len(tako)-1):
  for k in range(j+1, len(tako)):
      ans += tako[j] * tako[k]
print(ans)
v = list(map(int, input().split()))
v.sort()

while(len(v)!=2):
    v += [(v.pop(0)+v.pop(0))/2]
    v.sort()
print(sum(v)/2)

### FIXED CODE ###

# C
N = int(input())
v = list(map(int, input().split()))
v.sort()

while(len(v)!=2):
    v += [(v.pop(0)+v.pop(0))/2]
    v.sort()
print(sum(v)/2)
a,b=map(int,raw_input().split())
if a<b:
  print b*str(a)
else b<a:
   print b*str(a)
  

### FIXED CODE ###

a,b=map(int,raw_input().split())
if a<b:
  print b*str(a)
else:
   print a*str(b)
'Christmas' + (25 - D) * ' Eve'

### FIXED CODE ###

print('Christmas' + ' Eve' * (25 - int(input())))
[N,L] = [int(x) for x in input().split()]
A = dict
ANS = [10**9+1]*N
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    try : A[x] += [i]
    except KeyError : A[x] =  [i]
for i in set(A) :
    for j in A[i] :
        for k in range(L) :
            try :
                if ANS[j+k] == 10**9+1 : 
                    ANS[j+k] = i
                    count += 1
            except IndexError : continue
    if count == N : break
for i in ANS[L-1:-1]:
    print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
x = input()
x_int = int(x)
print x_int ** 3

### FIXED CODE ###

x = input()
y = x ** 3
print(y)
s = list(input())

ans = 0

for ss in s:
    ans += int(s)
print(ans)

### FIXED CODE ###

s = list(input())

ans = 0

for ss in s:
    ans += int(ss)
print(ans)
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

count = 0
for i in range(N):
	# print('B:',B[A[i]-1])
	# 追加の満足度が入らない場合は除く
	if i == 0:
		count += B[A[i]-1]
	else:
		count += B[A[i]-1]
		if abs(A[i]-A[i-1]) == 1:
			# print('C:',C[A[i-1]-1])
			count += C[A[i-1]-1]
print(count)


### FIXED CODE ###

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

count = 0
pre   = 0
for i in range(N):
	now = A[i] - 1
	count += B[now]
	if i != 0 and pre == now - 1:
		count += C[pre]
	pre = now
print(count)
list = input().split()
x,y,z = list[0],list[1],list[2]
x -= z * 2
num = x % (y+z)
if num >= y:
    print((x//(y+z))+1)
else:
    print(x//(y+z))


### FIXED CODE ###

list = input().split()
x,y,z = int(list[0]),int(list[1]),int(list[2])
x -= z * 2
num = x % (y+z)
if num >= y:
    print((x//(y+z))+1)
else:
    print(x//(y+z))
N = int(input())
A = list(map(int, input().split()))
print("YES" if len(set(A)) = N, else "NO")

### FIXED CODE ###

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

if len(set(A)) < len(A):
  print("NO")
else:
  print("YES")
def gcd(a,b):
    if a<b:
     d=a
     a=b
     b=d

    if b==0:
     b=1

    c=a%b

    if c==0:
     return b
    else:
     return gcd(b,c)

def lcm(a,b):
    c=gcd(a,b)
    return a/c*b



n=int(input())
t=[0]*n

for lop2 in range(n):
    t[lop2]=int(input())

ans=t[0]

for lop in range(1,n):
    ans=lcm(ans,t[lop])
print(int(ans))


### FIXED CODE ###

'''
def gcd(a,b):
    if a<b:
     c=a
     a=b
     b=c

    c=a%b

    if c==0:
     return b
    else:
     return gcd(b,c)
'''

def gcd(a,b):
    return a if b == 0 else gcd(b,a%b)

def lcm(e,f):
    c=gcd(e,f)
    g=e*f
    return g//c



n=int(input())
t=[0]*n

for lop2 in range(n):
    t[lop2]=int(input())

ans=t[0]

for lop in range(1,n):
    ans=lcm(ans,t[lop])
print(int(ans))
number = input()
a = number.split()

D=int(a[0])
N=int(a[1])

if D=0:
    print(N)
elif D=1:
    answer = 100*N
    print(answer)
elif D=2:
    answer = 10000*N
    print(answer)

### FIXED CODE ###

number = input()
a = number.split()

D=int(a[0])
N=int(a[1])

if N == 100:
    if D==0:
        print(N+1)
    elif D==1:
        answer = 100*N
        print(answer+100)
    elif D==2:
        answer = 10000*N
        print(answer+10000)

else:
    if D==0:
        print(N)
    elif D==1:
        answer = 100*N
        print(answer)
    elif D==2:
        answer = 10000*N
        print(answer)
from math import gcd
K = int(input())
sumval = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            g = math.gcd(math.gcd(a,b),c)
            sumval += g
print(sumval)

### FIXED CODE ###

import math
K = int(input())
sumval = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        f = math.gcd(a,b)
        for c in range(1, K+1):
            g = math.gcd(f,c)
            sumval += g
print(sumval)
n= int(input())
branchdict = {}
for i in range(n-1):
    a,b,c= map(int,input().split())
    branchdict[a-1] = branchdict.get(a-1,[]) + [(b-1,c)]
    branchdict[b-1] = branchdict.get(b-1,[]) + [(a-1,c)]
q,k= map(int,input().split())
cost = [0] * n
def dfs(curnode,pre,addcost):
    cost[curnode]=addcost
    passedf[curnode]=True
    if curnode in branchdict.keys():
        for abr in branchdict[curnode]:
            if abr[0]!=pre:
                dfs(abr[0],curnode,addcost+abr[1])
dfs(k-1,-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n= int(input())
bd = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c= map(int,input().split())
    bd[a-1].append((b-1,c))
    bd[b-1].append((a-1,c))
q,k= map(int,input().split())
cost = [0] * n
def dfs(curnode,pre,addcost):
    for abr in bd[curnode]:
        if abr[0]!=pre:
            cost[abr[0]]=addcost+abr[1]
            dfs(abr[0],curnode,addcost+abr[1])
dfs(k-1,-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])
n = int(input())
L = sorted(list(map(int,input().split())))
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        a,b = L[i],L[j]
        cnt += sum(abs(a-b)< l < a+b for l in L if l != a and l != b)
print(cnt//3)

### FIXED CODE ###

a,b =map(int,input().split())
print(max(a-2*b,0))
S=input()
N=len(S)
children=[1]*N
def next(children):
    new_children=[0]*N
    for i in range(N):
        if S[i]=='L':
            new_children[i-1]+=children[i]
        else:
            new_children[i+1]+=children[i]
    return new_children

change=[]
count=0
while True:

    #print(children)
    if children in change:
        start=change.index(children)
        break
    change.append(children)

    children=next(children)
    count += 1
#print(start, count)
if count==start:
    R=(10**100-4)%(count-start)
    print(' '.join(change[4+R]))
else:
    print(' '.join(change[start]))


### FIXED CODE ###

S=input()

N=len(S)

lst=[0]*N
R_count=0
for i in range(N-1):
    if S[i]=='R' and S[i+1]=='R':
        R_count+=1
    if S[i]=='R' and S[i+1]=='L':
        R_count += 1
        lst[i]=R_count
        R_count=0
L_count=0
for i in range(N-1, 0, -1):
    if S[i]=='L' and S[i-1]=='L':
        L_count+=1
    if S[i]=='L' and S[i-1]=='R':
        L_count += 1
        lst[i]=L_count
        L_count=0
#print(lst)
i=0
while i < N:
    if lst[i] and lst[i+1]:
        mid=(lst[i]+lst[i+1])//2
        if (lst[i]-lst[i+1])%2==0:
            lst[i], lst[i+1] = mid, mid
        elif lst[i]>lst[i+1]:
            if lst[i]%2==1:
                lst[i], lst[i+1]= mid+1, mid
            else:
                lst[i], lst[i+1] =mid, mid+1
        elif lst[i]<lst[i+1]:
            if lst[i+1]%2==1:
                lst[i], lst[i + 1] = mid, mid + 1
            else:
                lst[i], lst[i + 1] = mid + 1, mid
        i+=1
    i+=1
print(' '.join(list(map(str, lst))))
n,m=map(int,input().split())
#Union-Find木
#par[i]:iの親　deep[i]:iの深さ　size[i]:iの大きさ
par=[i for i in range(n)]
deep=[1]*n
size=[1]*n

#親を見つける
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])

#二つのグループを統合する
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1

#xとyが同じグループに属するかどうか
def same(x,y):
  return find(x)==find(y)

#xが属するグループの要素数を返す
def group_count(x):
  return size[find(x)]

#連結成分の個数を返す
def count():
  check=set()
  for i in par:
    parent=find(i)
    if parent not in check:
      check.add(parent)
  return len(check)

for i in range(m):
  a,b=map(int,input().split())
  unite(a,b)
print(count()-1)
    
  


### FIXED CODE ###

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

#Union-Find木
#par[i]:iの親　deep[i]:iの深さ　size[i]:iの大きさ
par=[i for i in range(n)]
deep=[1]*n
size=[1]*n

#親を見つける
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])

#二つのグループを統合する
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1

#xとyが同じグループに属するかどうか
def same(x,y):
  return find(x)==find(y)

#xが属するグループの要素数を返す
def group_count(x):
  return size[find(x)]
  
for i in range(m):
  a,b=map(int,input().split())
  unite(a-1,b-1)
  
from collections import Counter
x=[]
for i in par:
  x.append(find(i))
x=Counter(x)
print(len(x)-1)
n = int(input())
s = [input().split]
if len(set(s)) == 3:
    print('Three')
else:
    print('Four')

### FIXED CODE ###

n = int(input())
if n < 3:
    print(0)
else:
    print(n // 3)
j = 0
input = input()
a,b,c = map(int, input.split())
for i in range(a,b + 1)
    if c % i == 0
        j += 1
print(j)


### FIXED CODE ###

j = 0
input = input()
a,b,c = map(int, input.split())
for i in range(a,b + 1):
    if c % i == 0:
        j += 1
print(j)
from collections import defaultdict as dd
def main():
    N, M = map(int, input().split())

    MAP = [[0]*N for x in range(N)]
    E = []
    for m in range(M):
        a,b,c = map(int, input().split())
        MAP[a-1][b-1] = c
        E.append((a-1,b-1,c))

    dp = [-float('inf')]*N
    dp[0] = 0
    updated = set([0])
    for count in range(1, 2*N+1):  # N
        preupdated = list(updated)
        updated = set([])
        for e in preupdated:
            a,b,c = E[e]
            if max(dp[b], dp[b]) < dp[a] + c:
                updated.add(b)
                dp[b] = dp[a] + c
        if count == N-1:
            tmp = dp[N-1]

    # print(tmp, dp[N-1])
    if dp[N-1] == tmp:
        print(tmp)
    else:
        print('inf')


if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()



### FIXED CODE ###

import math 
from collections import defaultdict as dd
def main():
    N, M = map(int, input().split())

    MAP = [[]*N for x in range(N)]
    E = []
    for m in range(M):
        a,b,c = map(int, input().split())
        MAP[a-1].append((b-1, c))
        E.append((a-1,b-1,c))

    dp = [-float('inf')]*N
    dp[0] = 0
    updated = set([0])
    for count in range(1, 2*N+1):  # N
        preupdated = list(updated)
        updated = set([])
        for a in preupdated:
            for b,c in MAP[a]:
                if max(dp[b], dp[b]) < dp[a] + c:
                    updated.add(b)
                    dp[b] = dp[a] + c
        if count == N-1:
            tmp = dp[N-1]

    # print(tmp, dp[N-1])
    if dp[N-1] == tmp:
        print(tmp)
    else:
        print('inf')


if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()