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

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)] + [[True]+[False]*W+[True] for _ in range(H)] + [[True]*(W+2)]# '#'からの距離

for i in range(1,H+1):
  for j,c in enumerate(input(),1):
    if c == '#':
      visited[i][j] = True
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    for dx,dy in moves:
      xx = x+dx
      yy = y+dy
      if not visited[xx][yy]:
        visited[xx][yy] = True
        qq.append((xx,yy))
  q = qq
  
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

import math

k=int(input())+1
l=[]
for a in range(1,k):
    for b in range(1,k):
        for c in range(1,k):
            l.append(math.gcd(a,math.gcd(b,c)))
print (sum(l))

### FIXED CODE ###

import math

k=int(input())+1
l=[]
for a in range(1,k):
    for b in range(1,k):
        for c in range(1,k):
            l.append(math.gcd(a,math.gcd(b,c)))
print (sum(l))
### BUGGY CODE ###

#入力部
H, W = [int(i) for i in input().split()]
#mapの入力
mymap = [] #mapの配列
for i in range(H):
    mymap.append(list(input()))
Lmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列
Rmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列（逆順）
Umap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列
Dmap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列（逆順）

#Lmap
for i in range(H):
  mycnt = 1
  for j in range(W):
    if mymap[i][j] == '#':
      Lmap[i][j] = 0
      mycnt = 1
    else: 
      Lmap[i][j] = mycnt
      mycnt += 1

#Rmap
for i in range(H):
  mycnt = 1
  for j in reversed(range(W)):
    if mymap[i][j] == '#':
      Rmap[i][j] = 0
      mycnt = 1
    else: 
      Rmap[i][j] = mycnt
      mycnt += 1

#Umap
for i in range(W):
  mycnt = 1
  for j in range(H):
    if mymap[j][i] == '#':
      Umap[j][i] = 0
      mycnt = 1
    else: 
      Umap[j][i] = mycnt
      mycnt += 1

#Dmap
for i in range(W):
  mycnt = 1
  for j in reversed(range(H)):
    if mymap[j][i] == '#':
      Dmap[j][i] = 0
      mycnt = 1
    else: 
      Dmap[j][i] = mycnt
      mycnt += 1

      #最大値の検索
mymax = -99
for i in range(H):
  for j in range(W):
    if Lmap[i][j]+ Rmap[i][j]+ Umap[i][j]+ Dmap[i][j] > mymax:
      mymax = Lmap[i][j]+ Rmap[i][j]+ Umap[i][j]+ Dmap[i][j] 
      
print(mymax-3)

### FIXED CODE ###

import numpy as np
 
H, W = map(int, input().split())
#mapの入力
mymap = [] 
for i in range(H):
    mymap.append(list(input()))

#探索可能性をブーリアン表記
mymap = (np.array(mymap) == ".")
  
L = np.zeros((H, W), dtype=int) #左側から探索した場合の配列
R = np.zeros((H, W), dtype=int) #右側から探索した場合の配列
U = np.zeros((H, W), dtype=int) #上側から探索した場合の配列
D = np.zeros((H, W), dtype=int) #下側から探索した場合の配列

#列ごとに左から
for j in range(W):
  if j == 0: #左端
    L[:, j] = mymap[:, j] #true = 1, false = 0
  else:
    L[:, j] = (L[:, j - 1] + 1) * mymap[:, j] #trueの場合は1つ左の列の値を加算しながら

#列ごとに右から
for j in range(W - 1, -1, -1): #(引数：開始数，終了数，加算数）
  if j >= W - 1: #右端
    R[:, j] = mymap[:, j]
  else:
    R[:, j] = (R[:, j + 1] + 1) * mymap[:, j] 

#行ごとに上から
for i in range(H):
  if i <= 0: #上端
    U[i, :] = mymap[i, :]
  else:
    U[i, :] = (U[i - 1, :] + 1) * mymap[i, :]

#行ごとに下から
for i in range(H - 1, -1, -1):
  if i >= H - 1: #下端
    D[i, :] = mymap[i, :]
  else:
    D[i, :] = (D[i + 1, :] + 1) * mymap[i, :]

#総和から重複分(=3)の差をとって，最大値を出力
print(np.max(L + R + U + D - 3))
### BUGGY CODE ###

N,Q=map(int,input().split())
def find_par(x):
    u=x%N-1
    if u<=0:
        u+=N
    return (x-u-1)//N+1
def path(x):
    s_node=x
    d=[s_node]
    while s_node!=1:
        s_node=find_par(s_node)
        d.append(s_node)
    return d
for _ in range(Q):
    v,w=map(int,input().split())
    data1=set(path(v))
    data2=path(w)
    data2.sort(reverse=True)
    for num in data2:
        if num in data1:
            print(num)
            break

### FIXED CODE ###

N,Q=map(int,input().split())
if N>1:
    def find_par(x):
        u=x%N-1
        if u<=0:
            u+=N
        return (x-u-1)//N+1
    def path(x):
        s_node=x
        d=[s_node]
        while s_node!=1:
            s_node=find_par(s_node)
            d.append(s_node)
        return d
    for _ in range(Q):
        v,w=map(int,input().split())
        data1=set(path(v))
        data2=set(path(w))
        print(max(data1 & data2))
else:
    for _ in range(Q):
        v,w=map(int,input().split())
        print(min(v,w))
### BUGGY CODE ###

def list_difference(list1, list2):
    result = list1.copy()
    for value in list2:
        if value in result:
            result.remove(value)

    return len(result)


n=int(input())
a=[list(input()) for i in range(n)]
count=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        if list_difference(a[i],a[j])==0:
            count+=1
print(count)

### FIXED CODE ###

import math
import collections

n=int(input())
a=[list(input()) for i in range(n)]
b=[str(sorted(list(i))) for i in a]
count=list(collections.Counter(b).values())
count=[i for i in count if i>1]
print(int(sum([math.factorial(x)/(math.factorial(x-2)*2) for x in count])))
### BUGGY CODE ###

class Node:
    def __init__(self, id):
        self.id = id
        self.left = None
        self.right = None
        self.sibling = None
        self.parent = None

def preorder_tree_walk(root):
    result = []
    result.append(root.id)
    if root.left != None:
        result.extend(preorder_tree_walk(root.left))
    if root.right != None:
        result.extend(preorder_tree_walk(root.right))
    return result

def inorder_tree_walk(root):
    result = []
    if root.left != None:
        result.extend(inorder_tree_walk(root.left))
    result.append(root.id)
    if root.right != None:
        result.extend(inorder_tree_walk(root.right))
    return result

def insert(root, z):
    y = None
    x = root
    while x != None:
        y = x
        if z.id < x.id:
            x = x.left
        else:
            x = x.right
    z.parent = y

    if y == None:
        root = z
    elif z.id < y.id:
        y.left = z
    else:
        y.right = z
    return root

n = int(raw_input())
root = None
for i in xrange(n):
    line = raw_input().split()
    if line[0] == 'insert':
        num = int(line[1])
        root = insert(root, Node(num))
    elif line[0] == 'print':
        inorder = inorder_tree_walk(root)
        preoder = preorder_tree_walk(root)
        print ' ' + ' '.join(map(str, inorder))
        print ' ' + ' '.join(map(str, preoder))

### FIXED CODE ###

from __future__ import print_function
from sys import stdin
class Node:
    def __init__(self, id):
        self.id = id
        self.left = None
        self.right = None
        self.parent = None

def preorder_tree_walk(root):
    print('', root.id, end='')
    if root.left != None:
        preorder_tree_walk(root.left)
    if root.right != None:
        preorder_tree_walk(root.right)

def inorder_tree_walk(root):
    if root.left != None:
        inorder_tree_walk(root.left)
    print('', root.id, end='')
    if root.right != None:
        inorder_tree_walk(root.right)

def insert(root, z):
    y = None
    x = root
    while isinstance(x, Node):
        y = x
        if z.id < x.id:
            x = x.left
        else:
            x = x.right
    z.parent = y

    if y == None:
        root = z
    elif z.id < y.id:
        y.left = z
    else:
        y.right = z
    return root

n = int(raw_input())
root = None
for i in xrange(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        num = int(cmd[7:])
        root = insert(root, Node(num))
    else:
        inorder_tree_walk(root)
        print()
        preorder_tree_walk(root)
        print()
### BUGGY CODE ###

from collections import Counter
n,k=map(int,input().split())
a=Counter(list(map(int,input().split())))
cnt=0
ls=[]
if len(a)>k:
	for i in range(len(a)):
		ls.append(a.most_common()[i][1])
print(sum(ls[k:]))

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
ls=[0]*(n+1)
for i in a:
    ls[i]+=1
ls=sorted(ls,reverse=True)
for i in range(k,n+1):
    if ls[i]==0:
        break
    else:
        cnt+=ls[i]
print(cnt)
### BUGGY CODE ###

N,M = map(int,input().split())
from collections import defaultdict
hist = defaultdict(int)
AB = [[0,0]]*N
for n in range(N):
    temp = list(map(int,input().split()))
    if temp[0] <= M:
        AB[n] = temp
        hist[temp[0]] = temp[0]-1
work_schedule = [0]*M
sorted_AB = sorted(AB,key=lambda x:(-x[1],x[0]))
for work in sorted_AB:
    while True:
        if hist[work[0]] >= M:
            break
        elif work_schedule[hist[work[0]]] == 0:
            work_schedule[hist[work[0]]]  = work[1]
            break
        elif  work_schedule[hist[work[0]]] != 0:
            hist[work[0]] += 1
print(sum(work_schedule))

### FIXED CODE ###

from collections import defaultdict
import heapq

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

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

h = []
res = 0

for i in range(1, m + 1):
    if dct[i]:
        for item in dct[i]:
            heapq.heappush(h, item)
    if h:
        res += heapq.heappop(h)

print(-res)
### BUGGY CODE ###

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

flags = [True for i in range(N)]

count = 0
for i in range(N):
    if flags[i]:
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                flags[j] = False
            if A[j] == A[i]:
                flags[i] = False
        if flags[i]:
            count += 1
print(count)


### FIXED CODE ###

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

counts = [0 for i in range(Amax+1)]

for a in A:
    counts[a] += 1

count = 0
for i in range(1, Amax+1):
    if counts[i] == 1:
        count += 1
    if counts[i]:
        for j in range(i*2, Amax+1, i):
            counts[j] = 0
print(count)
### BUGGY CODE ###

import collections
n = input()
li = list(map(int,input().split()))
l_set = set(li)
ans_dic = {}
for i in l_set:
    temp = 0
    li2 = li[:]
    li2.remove(i)
    c = collections.Counter(li2)
    c_items = list(c.items())
    for j in c_items:
        temp += ((j[1] * (j[1]-1)) // 2)
    ans_dic[i] = temp
for k in li:
    print(ans_dic[k])

### FIXED CODE ###

import collections
temp = 0
n = input()
li = list(map(int,input().split()))
c = collections.Counter(li)
c_items = list(c.items())
for j in c_items:
    temp += ((j[1] * (j[1]-1)) // 2)
for i in li:
    print(temp - (c[i]-1))
### BUGGY CODE ###

from collections import deque
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

G = Graph()

N, Q = getlist()
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a, b)
	G.add_edge(b, a)

plus = [0 for i in range(N + 1)]
for i in range(Q):
	p, x = getlist()
	plus[p] += x


q = deque([]) 
ans = [0 for i in range(N)]
visit = [-1 for i in range(N + 1)]
visit[1] = 1
q.append(1)
while q:
	m = q.pop()
	visit[m] = 1
	ans[m - 1] += plus[m]
	x = ans[m - 1]
	for i in G.graph[m]:
		if visit[i] == -1:
			q.append(i)
			ans[i - 1] += x

print(" ".join(list(map(str, ans))))

### FIXED CODE ###

from collections import deque
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

G = Graph()

N, Q = getlist()
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a, b)
	G.add_edge(b, a)

plus = [0] * (N + 1)
for i in range(Q):
	p, x = getlist()
	plus[p] += x

q = deque([]) 
ans = [0] * N
visit = [-1] * (N + 1)
visit[1] = 1
q.append(1)
while q:
	m = q.pop()
	visit[m] = 1
	ans[m - 1] += plus[m]
	x = ans[m - 1]
	for i in G.graph[m]:
		if visit[i] == -1:
			q.append(i)
			ans[i - 1] += x

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

from math import log2, ceil


def bisect(array, x, left_limit):
    left = left_limit
    right = N
    # print(array, x, left, right)
    while left < right:
        target = (left + right) // 2
        if array[target] == x:
            if b[target]:
                return target
            idx = target - 1
            while array[idx] == x:
                if b[idx] and idx >= left:
                    return idx
                else:
                    idx -= 1
                    if idx < left:
                        break
            idx = target + 1
            while array[idx] == x:
                if b[idx]:
                    return idx
                else:
                    idx += 1
                if idx >= right:
                    break
            return -1
        elif array[target] < x:
            right = target
        else:  # array[target] > x
            left = target + 1
    return -1


N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = [True for _ in range(N)]

ans = 0
for i in range(N):
    if not b[i]: continue
    t = a[i]
    # print(a, b)
    idx = []
    for j in list(range(ceil(log2(t)), int(log2(t * 2)) + 1))[::-1]:
        pair = 2 ** j - t
        # print(t, pair)
        res = bisect(a, pair, i + 1)
        if res != -1:
            b[res] = False
            b[i] = False
            ans += 1
            break

print(ans)


### FIXED CODE ###

# https://beta.atcoder.jp/contests/agc029/submissions/3804087
from collections import Counter

N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = Counter(a)

ans = 0
for t in a:
    s = (1 << t.bit_length()) - t
    if t == s:
        ans += b[t] // 2
        b[t] %= 2
    else:
        u = min(b[s], b[t])
        ans += u
        b[s] -= u
        b[t] -= u

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

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]

f = True
day = 1
while(f):
  done = set()
  nokori_games = 0
  
  for m in range(n):
    nokori_games += len(a[m])
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].popleft()
        a[teki - 1].popleft()
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
  if not nokori_games:
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1


### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter
sys.setrecursionlimit(10**7)

def main():
    N = int(input())
    a = list(map(int,input().split()))
    active = []
    
    for i in range(N):
        active.append((a[i],i))
        
    active.sort(key=itemgetter(0),reverse=True)
    
    def point(x,y,ind):
        if ind == N:
            return 0
        else:
            ret1 = point(x+1,y,ind+1)+active[ind][0]*(abs(active[ind][1]-x))
            ret2 = point(x,y-1,ind+1)+active[ind][0]*(abs(active[ind][1]-y))
            ret = max(ret1,ret2)
            return ret
    
    print(point(0,N-1,0))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    N = int(input())
    a = list(map(int,input().split()))
    active = []
    
    for i in range(N):
        active.append((a[i],i))
        
    active.sort(key=itemgetter(0),reverse=True)
    dp = [[0]*(N+1) for _ in range(N+1)]
    
    for i in range(N):
        for j in range(i+1):
            x,y = j,i-j
            dp[x+1][y] = max(dp[x+1][y],dp[x][y]+active[x+y][0]*(abs(active[x+y][1]-x)))
            dp[x][y+1] = max(dp[x][y+1],dp[x][y]+active[x+y][0]*(abs(active[x+y][1]-(N-y-1))))

    ans = 0
    for i in range(N+1):
        ans = max(ans,dp[i][N-i])
        
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = [int(input()) for i in range(N)]
    idx = 0
    target = 1
    cnt = 1
    passed = []
    while True:
        if idx >= N:
            print(-1)
            return
        if A[idx]-1 == target:
            print(cnt)
            return
        if A[idx]-1 in passed:
            print(-1)
            return
        passed.append(idx)
        idx = A[idx]-1
        cnt += 1



if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = [int(input()) for i in range(N)]
    idx = 0
    target = 1
    cnt = 1
    passed = [False]*N
    while True:
        if idx >= N:
            print(-1)
            return
        if A[idx]-1 == target:
            print(cnt)
            return
        if passed[A[idx]-1]:
            print(-1)
            return
        passed[idx] = True
        idx = A[idx]-1
        cnt += 1



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

n, m = map(int, input().split())
s = set(range(1, n+1))
for i in range(m):
    l, r = map(int, input().split())
    s = s & set(range(l, r+1))
print(len(s))


### FIXED CODE ###

n, m = map(int, input().split())
ls = [0]*m
rs = [0]*m

for i in range(m):
  l, r  = map(int, input().split())
  ls[i] = l
  rs[i] = r

print(max(min(rs)-max(ls)+1,0))
### BUGGY CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h):
        a[i][0]=int(s[i][0]=='.')
        b[i][-1]=int(s[i][-2]=='.')
        for j in range(1,w):
            a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
            b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
    for j in range(w):
        c[0][j]=int(s[0][j]=='.')
        d[-1][j]=int(s[-1][j]=='.')
        for i in range(1,h):
            c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
            d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(sum(u)-3for t in zip(a,b,c,d)for u in zip(*t)))
main()

### FIXED CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()
### BUGGY CODE ###

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

def expect(p):
    return sum(range(1,p+1))/p

sums = []
for i in range(N-K+1):
    expect_sum = 0
    for j in range(K):
        expect_sum += expect(P[i+j])
    sums.append(expect_sum)

print(max(sums))


### FIXED CODE ###

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

P = [(1+p)/2 for p in P]

S = [P[0]]
for i in range(1,N):
    S.append(P[i]+S[i-1])

S.insert(0,0)

b = max([S[i]-S[i-K] for i in range(K, N+1)])

print(b)
### BUGGY CODE ###

N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

result = []
while q != []:
    qn = q.pop(0)
    result.append(qn)
    for v in outs[qn]:
        ins[v] -= 1
        if ins[v] == 0:
            q.append(v)


last = [0] * N
# last[i] = iが最後だったときに最長のパス
for sq in result:
    tp = last[sq] + 1
    for v in outs[sq]:
        last[v] = max(last[v], tp)

print(max(last))


     



### FIXED CODE ###

N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

result = []
while q != []:
    qn = q.pop()
    result.append(qn)
    for v in outs[qn]:
        ins[v] -= 1
        if ins[v] == 0:
            q.append(v)


last = [0] * N
# last[i] = iが最後だったときに最長のパス
for sq in result:
    for v in outs[sq]:
        last[v] = max(last[v], last[sq] + 1)

print(max(last))
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    graph[l-1].append((r-1, d))
    graph[r-1].append((l-1, -d))
seen = [False]*n
dist = [None]*n
for i in range(n):
    if seen[i]:
        continue
    q = deque([i])
    dist[i] = 0
    while q:
        node = q.popleft()
        seen[node] = True
        for c_node, d in graph[node]:
            if dist[c_node] is None:
                dist[c_node] = dist[node] + d
            elif dist[c_node] != dist[node] + d:
                print('No')
                exit(0)
            if not seen[c_node]:
                q.append(c_node)
print('Yes')

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    graph[l-1].append((r-1, d))
    graph[r-1].append((l-1, -d))
seen = [False]*n
dist = [None]*n
for i in range(n):
    if seen[i]:
        continue
    q = deque([i])
    dist[i] = 0
    while q:
        node = q.popleft()
        if seen[node]:
            continue
        seen[node] = True
        for c_node, d in graph[node]:
            if dist[c_node] is None:
                dist[c_node] = dist[node] + d
            elif dist[c_node] != dist[node] + d:
                print('No')
                exit(0)
            if not seen[c_node]:
                q.append(c_node)
print('Yes')