Harryxun/stf_run huggingface dataset:
import numpy as np
n, m = map(int, input().split())
lst = []
for _ in range(n):
    lst.append([0, 0])

for _ in range(m):
    p, s = input().split()
    p = int(p)
    if s == 'AC':
        lst[p-1][0] = 1
    elif lst[p-1][0] == 0:
        lst[p-1][1] += 1

correct = 0
wrong = 0
for i in range(n):
    correct += lst[i][0]
    wrong += lst[i][1]
print(correct, wrong)


### FIXED CODE ###

n, m = map(int, input().split())
lst = []
for _ in range(n):
    lst.append([0, 0])

for _ in range(m):
    p, s = input().split()
    p = int(p)
    if s == 'AC':
        lst[p-1][0] = 1
    elif lst[p-1][0] == 0:
        lst[p-1][1] += 1

correct = 0
wrong = 0
for i in range(n):
    correct += lst[i][0]
    if lst[i][0] == 1:
        wrong += lst[i][1]
print(correct, wrong)
N = int(input())
S = input()


class Node:
    def __init__(self, num_):
        self.num = num_
        self.children = {}  # dict

    def addChild(self, ch_, num_):
        self.children[ch_] = Node(num_)


ma_max = 0
Tr = {}
for i in range(0, N):
    tr = Tr
    ma = 0
    for j in range(i, N):
        if S[j] not in tr:
            tr[S[j]] = Node(j)
            tr = tr[S[j]].children
        else:
            if tr[S[j]].num >= i:
                ma = 0
            else:
                ma += 1
            tr = tr[S[j]].children
    ma_max = max(ma_max, ma)
    if N - i < ma_max:
        break

print(ma_max)

### FIXED CODE ###

S = input()
if S == "Sunny":
    print("Cloudy")
elif S == "Cloudy":
    print("Rainy")
elif S == "Rainy":
    print("Sunny")
import copyfrom fractions import gcd
N,X=map(int,input().split())
x=list(map(int,input().split()))
z=copy.deepcopy(x)+[X]
z.sort()

if N>1:
  y=[0]*N
  for i in range(N):
    y[i] = z[i+1]-z[i]
  ans=y[0]
  for j in range(N):
    ans = gcd(z[j],ans)
  print(ans)
else:
  print(abs(X-x[0]))

### FIXED CODE ###

import copy
from fractions import gcd
N,X=map(int,input().split())
x=list(map(int,input().split()))
z=copy.deepcopy(x)+[X]
z.sort()

if N>1:
  y=[0]*N
  for i in range(N):
    y[i] = z[i+1]-z[i]
  ans=y[0]
  for j in range(N):
    ans = gcd(y[j],ans)
  print(ans)
else:
  print(abs(X-x[0]))
import copy
a = list(input())
n = len(a)-1
ans = 0
for i in range(2 ** n):
    l=[]
    l = copy.copy(a)
    dokoka = [0]*(n)
    for j in range(n):
        if ((i >> j)&1):
            dokoka[j] = 1
    x = l.pop(0)
    while True:
      d = dokoka.pop(0)
      if d == 0:
          x += l.pop(0)
      else:
          ans += int(x)
          x = l.pop(0)
      if not dokoka:
          ans += int(x)
          break
print(ans)

### FIXED CODE ###

import copy
a = list(input())
n = len(a)-1
ans = 0
if n == 0:
  print(int(a[0]))
else:
  for i in range(2 ** n):
    l=[]
    l = copy.copy(a)
    dokoka = [0]*(n)
    for j in range(n):
        if ((i >> j)&1):
            dokoka[j] = 1
    x = l.pop(0)
    while True:
      d = dokoka.pop(0)
      if d == 0:
          x += l.pop(0)
      else:
          ans += int(x)
          x = l.pop(0)
      if not dokoka:
          ans += int(x)
          break
  print(ans)
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
inf = 10**18
N = int(input())
S = []
C = []
for i in range(N):
    s,c = input().split()
    S.append(s)
    C.append(int(c))
    
d_l = defaultdict(lambda:inf)
def left(s1):
    res = inf
    if s1==s1[::-1]:
        return 0
    if d_l[s1] != inf:
        return d_l[s1]
    for i in range(N):
        s2 = S[i][::-1]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    d_l[s1] = res
    return res

d_r = defaultdict(lambda:inf)
def right(s2):
    res = inf
    if s2==s2[::-1]:
        return 0
    if d_r[s2] != inf:
        return d_r[s2]
    for i in range(N):
        s1 = S[i]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    d_r[s2] = res
    return res

ans = inf
for i in range(N):
    ans = min(ans,left(S[i])+C[i])

if ans == inf:
    ans = -1

print(ans)


### FIXED CODE ###

def main(R,C,K,V):
    dp = [0]*(4*R*C)
    dp[1+4*0+4*C*0] = V[0][0]
    for k in range(4*R*C):
        n = k%4
        j = k//4%C
        i = k//(4*C)
        if n!=0:
            if i != 0 and n==1:
                dp[k] = max(dp[k-4*C-n:k-4*C-n+4])+V[i][j]
            if j != 0:
                dp[k] = max(dp[k],dp[k-4],dp[k-5]+V[i][j])
        if n==0:
            if i != 0:
                dp[k] = max(dp[k-4*C-n:k-4*C-n+4])

    print(max(dp[-5:-1]))

if __name__ == '__main__':
    R,C,K = map(int,input().split())
    C += 1
    rcv = [list(map(int,input().split())) for _ in range(K)]
    V = [[0]*C for _ in range(R)]
    for i in range(K):
        r,c,v = rcv[i]
        r -= 1
        c -= 1
        V[r][c] = v
    main(R,C,K,V)
import sys
bingo_size = 3
a = []
an = set()
for _ in range(3):
  a.append(list(map(int, input().split())))
  for i in a[_]:
    an.add(i)

n = int(input())
b = set()
for _ in range(n):
  bi = int(input())
  if bi in an:
    b.add(bi)

for hi in range(3):
  ok = True
  for _ in range(3):
    if a[hi][_] not in b:
      ok = false
      break
    if ok:
      print("Yes")

for wi in range(3):
  ok = True
  for _ in range(3):
    if a[_][wi] not in b:
      ok = false
      break
  if ok:
    print("Yes")

if all([a[0][0] in b, a[1][1] in b, a[2][2] in b]) or all([a[0][2] in b, a[1][1] in b, a[2][0] in b]):
           print("Yes")
           
print("No")   

### FIXED CODE ###

import sys
bingo_size = 3
a = []
an = set()
for _ in range(3):
  a.append(list(map(int, input().split())))

n = int(input())
b = set()
for _ in range(n):
  bi = int(input())
  b.add(bi)

for hi in range(3):
  ok = True
  for _ in range(3):
    if a[hi][_] not in b:
      ok = False
      
  if ok:
    print("Yes")
    sys.exit()

for wi in range(3):
  ok = True
  for _ in range(3):
    if a[_][wi] not in b:
      ok = False
      
  if ok:
    print("Yes")
    sys.exit()

if all([a[0][0] in b, a[1][1] in b, a[2][2] in b]) or all([a[0][2] in b, a[1][1] in b, a[2][0] in b]):
           print("Yes")
           sys.exit()
           
print("No")
n = int(input())
r = int(input())

if n >= 10:
    print(int(r))
else:
    a = 100*(10-n)
    print(int(r+a))

### FIXED CODE ###

inputStr = input()
inputList = inputStr.split(' ')
n = int(inputList[0])
r = int(inputList[1])

if n >= 10:
    print(int(r))
else:
    a = 100*(10-n)
    print(int(r+a))
s = input()
k = int(input())
flag = 1
for i in range(k):
    if s[i]!='1':
        flag = 0
        break
if flag:
    print(1)
else:
    print(s[1])


### FIXED CODE ###

s = input()
k = int(input())
flag = 1
for i in range(min(k,len(s))):
    if s[i]!='1':
        flag = 0
        a = s[i]
        break
if flag:
    print(1)
else:
    print(a)
S = str(input())
counter = 0
series = []

for i in S:
    if i == 'A' or i == 'T' or i == 'C' or i == 'G':
        counter += 1
    else:
        series.append(counter)
        counter = 0

print(max(series))


### FIXED CODE ###

S = str(input())
counter = 0
max = 0

for i in S:
    if i == 'A' or i == 'T' or i == 'C' or i == 'G':
        counter += 1
        if counter >= max:
            max = counter
    else:
        counter = 0

print(max)
import math
N, K = map(int, input().split())

M = []
x = 1
while x < 10 ** 5:
    M.append(1 / x)
    x <<= 1

p1 = max((N - K + 1) / N, 0)
p = 0
for i in range(1, min(N + 1, K)):
    t = int(math.log2(K / i)) + 1
    if K % i == 0 and  (K // i) & (K // i - 1) == 0:
        t -= 1
    p += M[t]
print(p / N + p1)


### FIXED CODE ###

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

M = []
x = 1
while x < (10 ** 5) * 2:
    M.append(1 / x)
    x <<= 1

p1 = max((N - K + 1) / N, 0)
p = 0
for i in range(1, min(N + 1, K)):
    t = int(math.log2(K / i)) + 1
    if K % i == 0 and  (K // i) & (K // i - 1) == 0:
        t -= 1
    p += M[t]
ans = p / N + p1
print('{0:.10f}'.format(ans))
import math

def is_prime(x):
    if x == 2:
        return True

    if (x == 1) or (x % 2 == 0):
        return False

    for i in range(3, math.ceil(math.sqrt(x))+1, 2):
        if x % i == 0:
            return False

    return True
    
if __name__ == '__main__':
    element_number = int(input())

    output = 0
    for x in map(int, sys.stdin.readlines()):
        if(is_prime(x)):
            output += 1

    print(output)

### FIXED CODE ###

import sys
import math

def is_prime(x):
    if x == 2:
        return True

    if (x == 1) or (x % 2 == 0):
        return False

    for i in range(3, math.ceil(math.sqrt(x))+1, 2):
        if x % i == 0:
            return False

    return True
    
if __name__ == '__main__':
    element_number = int(input())

    output = 0
    for x in map(int, sys.stdin.readlines()):
        if(is_prime(x)):
            output += 1

    print(output)
def security(s):

    return "Good" if s[0] != s[1] and s[1] != s[2] and s[2] != s[3] else "Bad"
def main():
    s = list(int(input()))
    print(security(s))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def security(s):

    return "Good" if s[0] != s[1] and s[1] != s[2] and s[2] != s[3] else "Bad"
def main():
    s = list(str(input()))
    print(security(s))

if __name__ == '__main__':
    main()
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from operator import itemgetter
from heapq import heappop, heappush
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M = inpl()
D = [0] + [10**18]*(N-1)
g0 = itemgetter(0)
Q = sorted([inpl() for _ in range(M)], key=g0, reverse=True)
#print(*Q, sep="\n")

HQ = [(0, 0)]

for i in range(N):
    while HQ[0][1] < i:
        heappop(HQ)
    v = HQ[0][0]
    while len(Q) and (i == (Q[-1][0]-1)):
        l, r, c = Q.pop()
        heappush(HQ, (v+c, r-1))


if v == 10**18:
    print(-1)
else:
    print(v)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from operator import itemgetter
from heapq import heappop, heappush
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M = inpl()
D = [0] + [10**18]*(N-1)
g0 = itemgetter(0)
Q = sorted([inpl() for _ in range(M)], key=g0, reverse=True)
#print(*Q, sep="\n")

HQ = [(0, 0), (10**18, N)]

for i in range(N):
    while HQ[0][1] < i:
        heappop(HQ)
    v = HQ[0][0]
    while len(Q) and (i == (Q[-1][0]-1)):
        l, r, c = Q.pop()
        heappush(HQ, (v+c, r-1))


if v == 10**18:
    print(-1)
else:
    print(v)
X,N=map(int,input().split())
p=list(map(int,input().split()))
m=X
for i in range(101):
    diff=abs(X-i)
    if i not in p and diff<m and diff!=m:
        m=diff
        ans=i
print(ans)

### FIXED CODE ###

X,N=map(int,input().split())
p=list(map(int,input().split()))
diff=102
for i in range(102):
    if i not in p and abs(X-i)<diff:
        diff=abs(X-i)
        ans=i
print(ans)
# https://abc096.contest.atcoder.jp/tasks/abc096_d

import itertools


def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False

    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1

    return True


N = int(input())


l = []

n = 2
while len(l) < N * 3:
    if is_prime(n):
        l.append(n)
    n += 1


for a in itertools.combinations(l, N):
    # print(a)
    is_ok = True
    for c in itertools.combinations(a, 5):
        if is_prime(sum(c)):
            # print(str(c) + ' is prime = ' + str(sum(c)))
            is_ok = False
            break
    if is_ok:
        print(' '.join(map(str, a)))
        break



### FIXED CODE ###




a, b = map(int, input().split())

# print(a)
# print(b)

m = a - 1
n = 1 if b >= a else 0

print(str(m + n))
N=int(input())
S=input()
K=int(input())
letter=""

for i in S:
    if i is S[K]:
        letter +=i
    else:
        letter +="*"
print(letter)


### FIXED CODE ###


N=int(input())
S=input()
K=int(input())
letter=""

for i in S:
    if i is S[K-1]:
        letter +=i
    else:
        letter +="*"
print(letter)
import sys
for line in sys.stdin;
    items_sorted = sorted( line.split() , reverse=True )
    print( "{} {}".format( items_sorted[0],items_sorted[1]) )

### FIXED CODE ###

from sys import stdin

for line in range(3000 + 5):
    x , y = map( int, stdin.readline().split() )

    if not ( x + y):
       break

    if x > y:
       x , y = y , x

    print(x, y)
# -*- coding: utf-8 -*-
import sys
import math
# sys.setrecursionlimit(10000)


def main():
    # 入力処理
    N, M = map(int, input().split())

    # アルゴリズム本体
    K = int(M / 2)

    # 出力
    print(K)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10000)


def main():
    # 入力処理
    N = int(input())

    # アルゴリズム本体
    x = 800 * N
    y = 200 * int(N / 15)

    # 出力
    print(x-y)


if __name__ == '__main__':
    main()
# -*- coding:utf-8 -*-

def main():
    n=int(input())

    for i in range(n):
        x1,y1,x2,y2,x3,y3,x4,y4=map(float,input().split())
        a=(y2-y1)/(x2-x1)
        b=(y4-y3)/(x4-x3)

        if a==b:
            print("YES")
        else:
            print("NO")
    
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def main():
    for i in range(int(input())):
        x1,y1,x2,y2,x3,y3,x4,y4=map(float,input().split())

        if abs((x2-x1)*(y4-y3)-(x4-x3)*(y2-y1))<1e-10:
            print("YES")
        else:
            print("NO")
    
        
if __name__ == '__main__':
    main()
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

AN=[]
for _ in range(N):
    AN.append(list(input()))
    
#print(AN)

AM=[]
for _ in range(M):
    AM.append(list(input()))

#print(AM)
for i in range(N-M+1):
    flag=False
    for j in range(N-M+1):
        if AN[i][j:j+M]==AM[0]:
            for k in range(i,i+M):
                if AN[k][j:j+M]!=AM[k]:
                    flag=True
                    break
            if flag:
                break
            print("Yes")
            exit()
                    

print("No")

### FIXED CODE ###

# coding: utf-8
# Your code here!
N,M=map(int,input().split())

AN=[]
for _ in range(N):
    AN.append(list(input()))
    
#print(AN)

AM=[]
for _ in range(M):
    AM.append(list(input()))

#print(AM)
for i in range(N-M+1):
    for j in range(N-M+1):
        #print(i,j)
        flag=True
        for k in range(M):
            if AN[i+k][j:j+M]!=AM[k]:
                #print(AN[i+k][j:j+M],AM[k])
                flag=False
        if flag:
            print("Yes")
            exit()
        
print("No")
# coding:utf-8

K, A, B = [int(i) for i in input().split()]
print(K, A, B)

def cal(K, A, B):
    BNUM = 1
    TRANS_GET = B - A
    # 操作開始
    counter = 0
    while counter < K:
        nokori = K - counter
        if BNUM >= A:
        # 交換可能
            if nokori >= 2:
                BNUM += TRANS_GET
                counter += 2
            else:
                BNUM += nokori
                break
        else:
        # 交換不可
            atonanko = A - BNUM
            if atonanko < nokori-2:
                BNUM += atonanko
                counter += atonanko
            else:
                BNUM += nikori
                break
    return BNUM


if A < B:
    if B - A > 2:
        max_b = cal(K, A, B)
    else:
        max_b = 1 + K
else:
    max_b = 1 + K

print(max_b)

### FIXED CODE ###

# coding:utf-8

K, A, B = [int(i) for i in input().split()]

def cal(K, A, B):
    BNUM = 1
    TRANS_GET = B - A
    # 操作開始
    counter = 0
    while counter < K:
        nokori = K - counter
        if BNUM >= A:
        # 交換可能
            if nokori >= 2:
                syou = int(nokori / 2)
                BNUM += TRANS_GET * syou
                counter += syou * 2
            else:
                # 叩く
                BNUM += 1
                counter += 1
        else:
        # 交換不可
            atonanko = A - BNUM
            if atonanko <= nokori-2:
                BNUM += atonanko
                counter += atonanko
            else:
                BNUM += nokori
                break
    return BNUM


if B - A <= 2:
    max_b = 1 + K
else:
    max_b = cal(K, A, B)

print(max_b)
input1 = list(map(int,input("").split(" ")))
A = list(map(int,input("").split(" ")))
N = input1[0]
K = input1[1]

flag = True
for i in range(N-3):
	if abs(A[i]-A[i+1]) != abs(A[i+2]-A[i+1]):
		flag = False
		break

if K in A:
	flag = true

if flag==True:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

### FIXED CODE ###

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

input1 = list(map(int,input("").split(" ")))
A = list(map(int,input("").split(" ")))
N = input1[0]
K = input1[1]

temp = A[0]
for i in range(1,N):
	temp = gcd(temp,A[i])

if K <= max(A) and K % temp == 0:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')
N, Q = map(int, input().split())
S = " " + input()
l = []
r = []
for _ in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
#CofAC= [-1] * (N + 1) #ACのC部分が何文字目か記録
#print([i for i, x in enumerate(l_dup) if x == 'a'])
# [0, 4]
#print([i for i, x in enumerate(S) if x == 'AC'])
dp = [0] * (N + 2) #i文字目から何個ACがあるか
for i in range(1, N + 1):
    dp[i] = S[i:].count("AC")
#print(dp)
ans = 0
for q in range(Q):
    ans = dp[l[q]] - dp[r[q] + 1]
    if S[r[q]] == "A" and S[r[q] + 1] == "C":
        ans -= 1
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = " " + input()
l = []
r = []
for _ in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
dp = [0] * (N + 2) #i文字目から何個ACがあるか
cnt = 0
for i in range(1, N):
    if S[-i] == "C" and S[-i-1] == "A":
            cnt += 1
    dp[N-i] = cnt
#print(dp)
ans = 0
for q in range(Q):
    ans = dp[l[q]] - dp[r[q] + 1]
    if r[q] < N:
        if S[r[q]] == "A" and S[r[q] + 1] == "C":
            ans -= 1
    print(ans)
h, w = map(int, input().split())
arr = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    arr[i] = list(input())

def isWay(x, y):
    if x >= 0 and x < w and y >= 0 and y < h and arr[x][y] == '.':
        return True
    else:
        return False

numWay = 0
for i in range(w):
    for j in range(h):
        if arr[i][j] == '.':
            numWay += 1

queue = [[0, 0]]
arr[0][0] = 1
while 1:
    if len(queue) == 0:
        break
    cell = queue[0]
    queue.pop(0)
    x = cell[0]
    y = cell[1]
    n = arr[x][y]
    if(isWay(x-1, y)):
        arr[x-1][y] = n+1
        queue.append([x-1, y])
    if(isWay(x+1, y)):
        arr[x+1][y] = n+1
        queue.append([x+1, y])
    if(isWay(x, y-1)):
        arr[x][y-1] = n+1
        queue.append([x, y-1])
    if(isWay(x, y+1)):
        arr[x][y+1] = n+1
        queue.append([x, y+1])
print(numWay - arr[w-1][h-1])

### FIXED CODE ###

h, w = map(int, input().split())
arr = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    arr[i] = list(input())

def isWay(x, y):
    if x >= 0 and x < h and y >= 0 and y < w and arr[x][y] == '.':
        return True
    else:
        return False

numWay = 0
for i in range(h):
    for j in range(w):
        if arr[i][j] == '.':
            numWay += 1

queue = [[0, 0]]
arr[0][0] = 1
while 1:
    if len(queue) == 0:
        break
    cell = queue[0]
    queue.pop(0)
    x = cell[0]
    y = cell[1]
    n = arr[x][y]
    if(isWay(x-1, y)):
        arr[x-1][y] = n+1
        queue.append([x-1, y])
    if(isWay(x+1, y)):
        arr[x+1][y] = n+1
        queue.append([x+1, y])
    if(isWay(x, y-1)):
        arr[x][y-1] = n+1
        queue.append([x, y-1])
    if(isWay(x, y+1)):
        arr[x][y+1] = n+1
        queue.append([x, y+1])
if arr[h-1][w-1] == '.':
    print(-1)
else:
    print(numWay - arr[h-1][w-1])
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(s,u):
  if u==N:
    reachable_list[s]=True
    return True
  
  visited[u]=True
  for v in graph[u]:
    check_reachable(s,v)    
  return False

reachable_list=[False]*(N+1)
for i in range(1,N+1):
  visited=[False]*(N+1)
  res=check_reachable(i,i)
#print(reachable_list)
  
elist2=[]
for a,b,nc in elist:
  if reachable_list[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(s,u):
  if u==N:
    reachable_list[s]=True
    return True
  
  visited[u]=True
  for v in graph[u]:
    if not visited[v]:
      check_reachable(s,v)    
  return False

reachable_list=[False]*(N+1)
for i in range(1,N+1):
  visited=[False]*(N+1)
  check_reachable(i,i)
#print(reachable_list)
  
elist2=[]
for a,b,nc in elist:
  if reachable_list[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])
s=input()
q=int(input())
for _ in range(q):
	k=input()
	if k[0] == "1":
		s = s[::-1]
	else:
		if k[2] == "1":
			s = k[4:]+s
		else:
			s = s+k[4:]
print(s)

### FIXED CODE ###

s=input()
if s=="AAA" or s=="BBB":
  print("No")
else:
  print("Yes")
N, M = map(int, input().split())
connected = {}

for i in range(M):
    a, b = map(int, input().split())
    connected.setdefault(a, 0)
    connected.setdefault(b, 0)
    connected[a] += 1
    connected[b] += 1

for i in range(1, N + 1):
    print(connected[i])


### FIXED CODE ###

N, M = map(int, input().split())
G = [[0 for i in range(N)] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a - 1][b - 1] += 1
    G[b - 1][a - 1] += 1
for i in range(N):
    s = 0
    for j in range(N):
        s += G[i][j]
    print(s)
w,a,b = map(int,input().split())
if w+a => b:
  print(0)
else:
	print(b-(a+w))


### FIXED CODE ###

w,a,b = map(int,input().split())

if abs(a-b) <= w:
  print(0)
else:
  print(abs(a-b)-w)
class sort1:
    def __init__(self, num):
        self.num = num
 
    def p_insert(self, lst):
        print(*lst)
        for i in range(1,self.num):
            j = i - 1
            while (j >= 0) * (lst[j] > lst[i]):
                j -= 1
            lst[j+1:i+1] = lst[i] , *lst[j+1:i]
            print(*lst)

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

s = sort1(n)
s.p_insert(l)

### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
for i in range(n):
    li = lst[i]
    j = i-1
    while j >= 0 and lst[j] > li:
        lst[j:j+2] = lst[j+1], lst[j]
        j -= 1
    print(*lst)