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

N=int(input())
E=[tuple(sorted(map(int,input().split()))) for i in range(N-1)]

DICT={x:ind for ind,x in enumerate(E)}

EDGE=[[] for i in range(N+1)]
for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)


M=int(input())
Q=[tuple(map(int,input().split())) for i in range(M)]

def dfs(x,y):
    USE=[-1]*(N+1)
    USE[x]=0

    NOW=[x]

    while NOW:
        n=NOW.pop()

        for to in EDGE[n]:
            if USE[to]==-1:
                USE[to]=n
                NOW.append(to)

    ANS=[y]
    while y!=x:
        y=USE[y]
        ANS.append(y)

    RET=[]

    for i in range(1,len(ANS)):
        RET.append(DICT[tuple(sorted([ANS[i-1],ANS[i]]))])

    return set(RET)

Q2=[dfs(x,y) for x,y in Q]

DP=[0]*(1<<M)
DP[0]=1

for i in range(N-1):
    B=0
    for k in range(M):
        if i in Q2[k]:
            B+=1<<k
        
    for j in range((1<<M)-1,-1,-1):
        DP[j|B]+=DP[j]

print(DP[-1])
        
    


### FIXED CODE ###

N=int(input())
E=[tuple(sorted(map(int,input().split()))) for i in range(N-1)]

DICT={x:ind for ind,x in enumerate(E)}

EDGE=[[] for i in range(N+1)]
for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)


M=int(input())
Q=[tuple(map(int,input().split())) for i in range(M)]

def dfs(x,y):
    USE=[-1]*(N+1)
    USE[x]=0

    NOW=[x]

    while NOW:
        n=NOW.pop()

        for to in EDGE[n]:
            if USE[to]==-1:
                USE[to]=n
                NOW.append(to)

    ANS=[y]
    while y!=x:
        y=USE[y]
        ANS.append(y)

    RET=[]

    for i in range(1,len(ANS)):
        RET.append(DICT[tuple(sorted([ANS[i-1],ANS[i]]))])

    return set(RET)

Q2=[dfs(x,y) for x,y in Q]

DP=[0]*(1<<M)
DP[0]=1

for i in range(N-1):
    B=0
    for k in range(M):
        if i in Q2[k]:
            B+=1<<k
        
    for j in range((1<<M)-1,-1,-1):
        DP[j|B]+=DP[j]

print(DP[-1])
### BUGGY CODE ###

n, k = map(int, input().split())
s = input()

happy_count = 0
pre = ''
for index, si in enumerate(list(s)):
  if index == 0:
    continue
  if list(s)[index - 1] == si:
    happy_count += 1

print(min(happy_count + (2 * k), n-1))


### FIXED CODE ###

n, k = map(int, input().split())
s = input()

happy_count = 0
pre = ''
for index in range(n - 1):
  if s[index + 1] == s[index]:
    happy_count += 1

print(min(happy_count + (2 * k), n-1))
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())),reverse=True)
score = [A[0]]
s = 0

for a in A[1:N]:
    s += score[0]
    score = score[1:] + [a,a]

print(s)

### FIXED CODE ###

import math
N = int(input())
A = sorted(list(map(int, input().split())),reverse=True)
s = A[0]

for i in range(1,N-1):
    s += A[math.ceil(i/2)]

print(s)
### BUGGY CODE ###

n = int(input())
s = input()

r = 0
g = 0
b = 0

for v in s:
    if v == 'R':
        r += 1
    elif v == 'G':
        g += 1
    else:
        b += 1

ans = r*g*b

for i in range(0, n - 2):
    for j in range(i + 1,  n - 1):
        for k in range(j  + 1, n):
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k] and j - i == k - j:
                ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = s.count('R')*s.count('G')*s.count('B')  # ここはただ簡潔にしただけ

for i in range(0, n - 2):
    for j in range(i + 1,  n - 1):
        k = (j - i) + j
        if k >= n:
            continue
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

n, k = [int(item) for item in input().split()]
a = sorted([int(item) for item in input().split()], reverse=True)

sum_possibility = [0] * 10001
sum_possibility[0] = 1

for i in range(n+1):
    if sum(sum_possibility[max(0, k-sum(a[i:])):k]) == 0:
        break
    for j in range(10000, -1, -1):
        if sum_possibility[j] is not 0 and j + a[i] < 10001:
            sum_possibility[j + a[i]] = 1
print(n-i)

### FIXED CODE ###

n, k = [int(item) for item in input().split()]
a = sorted([int(item) for item in input().split()], reverse=True)

count = 0
asum = 0
for item in a:
    if asum + item < k:
        asum += item
        count += 1
    else:
        count = 0

print(count)
### BUGGY CODE ###

from collections import deque
def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        cnt=visited[y][x]
        
        for dy,dx in move:
            my,mx=y+dy,x+dx 
            if not(0<=my<tate and 0<=mx<yoko):
                continue
            if maze[my][mx]=="#":
                continue
            if visited[my][mx]>cnt:
                queue.append([my,mx])
                visited[my][mx]=cnt # visitedは距離も兼ねてる
        for my in range(y-2,y+3):
            for mx in range(x-2,x+3):
                if not(0<=my<tate and 0<=mx<yoko):
                    continue
                if maze[my][mx]=="#":
                    continue
                if visited[my][mx]>cnt+1:
                    queue.append([my,mx])
                    visited[my][mx]=cnt+1
    if visited[gy][gx]==inf:
        print(-1)
    else:
        print(visited[gy][gx])


tate,yoko=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
maze=[]
inf=float('inf')
visited=[[inf]*yoko for i in range(tate)]

for i in range(tate):
    line=list(input())
    maze.append(line)
bfs()




### FIXED CODE ###

from collections import deque
def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        cnt=visited[y][x]
        
        for dy,dx in move:
            my,mx=y+dy,x+dx 
            if my<0 or my>=tate:
                continue
            if mx<0 or mx>=yoko:
                continue
            if maze[my][mx]=="#":
                continue
            if visited[my][mx]>cnt:
                queue.appendleft([my,mx])
                visited[my][mx]=cnt # visitedは距離も兼ねてる
        for my in range(y-2,y+3):
            for mx in range(x-2,x+3):
                if my<0 or my>=tate:
                    continue
                if mx<0 or mx>=yoko:
                    continue
                if maze[my][mx]=="#":
                    continue
                if visited[my][mx]>cnt+1:
                    queue.append([my,mx])
                    visited[my][mx]=cnt+1
    if visited[gy][gx]==inf:
        print(-1)
    else:
        print(visited[gy][gx])


tate,yoko=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
maze=[]
inf=float('inf')
visited=[[inf]*yoko for i in range(tate)]

for i in range(tate):
    line=list(input())
    maze.append(line)
bfs()
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
X = 1
for i in range(K):
    X *= A[i]
Y = X
for i in range(K, N):
    X = X * A[i] // A[i-K]
    if Y < X:
        print("Yes")
    else:
        print("No")
    Y = X

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(K, N):
    if A[i-K] < A[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
queue = []
s_i = 0
for i in range(N):
    tmp = 0
    for b, last in queue[s_i:]:
        if XH[i][0] > last:
            s_i += 1
        else:
            tmp += b

    bomb[i] -= tmp
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        queue.append([bomb[i], XH[i][0] + 2 * D])

print(ans)


### FIXED CODE ###

from collections import deque


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


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
dq = deque()
s_i = 0
sum_q = 0
for i in range(N):
    while dq and dq[0][1] < XH[i][0]:
        b, _ = dq.popleft()
        sum_q -= b

    bomb[i] -= sum_q
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        sum_q += bomb[i]
        dq.append([bomb[i], XH[i][0] + 2 * D])

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

from collections import deque

N = int(input())

A = [
  int(j) - i  for i, j in enumerate(input().split())
]


ans = 0
d = deque(A)
for i in range(N):
  a = d.popleft()
  c = d.count(-a - 2 * i)
  ans += c
print(ans)

### FIXED CODE ###

from collections import deque, Counter

N = int(input())

A = [
  int(j) - i  for i, j in enumerate(input().split())
]
cnt_A = Counter(A)

ans = 0
d = deque(A)
for i in range(N):
  a = d.popleft()
  #c = d.count(-a - 2 * i)
  c = cnt_A[-a - 2 * i]
  ans += c
print(ans)
### BUGGY CODE ###

N=input()
S=raw_input()

ans=0
for i in range(N):
	for j in range(i+1,N):
		s=S[i:j]
		if s in S[j:]:
			ans=max(ans,len(s))

print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
N=input()
s=raw_input()

str="abcdefghijklmnopqrstuvwxyz"
D={}
for i,str in enumerate(str):
	D[str]=i+1

base=27
mod=2**61-1
hash=[]

for i,x in enumerate(s):
	if i==0: hash.append(D[x]%mod)
	else: hash.append( (hash[-1]*base+D[x])%mod )

def get(l,r):
	if l==0: return hash[r-1]%mod
	else: return ( hash[r-1]-hash[l-1]*pow(base,(r-l),mod) )%mod

# 長さmを固定し、区間 [i, i + m) のハッシュ値を求めて、長さmの共通文字列があるかを判定
def check(m):
	C={}
	for i in range(N):
		if i+m<=N:
			hash_value=get(i,i+m)
			if hash_value in C:
				if m<=i-C[hash_value]:
					return True
			else:
				C[hash_value]=i
	else:
		return False

l=0
h=N

while 1<(h-l):
	m=(l+h)/2
	if check(m):
		l=m
	else:
		h=m

print l
### BUGGY CODE ###


import fractions

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

g=fractions.gcd(A,B)

if g==1:
    print(1)
    exit()
cnt=0
for i in range(2,g+1):
    if g%i==0:
        cnt+=1
        g=g//i
        while g%i==0:
            g=g//i
    if g==1:
        break
print(cnt+1)





### FIXED CODE ###

def div(N):
    ans = []
    for i in range(1, int(N ** 0.5) + 1):
        if N % i == 0:
            ans.append(i)
            if N // i != i:
                ans.append(N // i)
    ans.sort()
    return ans
import fractions

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

g=fractions.gcd(A,B)

if g==1:
    print(1)
    exit()
cnt=0
di=div(g)

for i in di:
    f=True
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            f=False
            break
    if f:
        cnt+=1
print(cnt)
### BUGGY CODE ###

# ダイナミック・プログラミング

INF = float('inf')

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

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])


### FIXED CODE ###

# ダイナミック・プログラミング
# PythonではTLEを起こしてしまう例

INF = float('inf')

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

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])
### BUGGY CODE ###



def sieveOfEratosthenes(N, s):

    
    prime = [False] * (N+1)

   
    for i in range(2, N+1, 2):
        s[i] = 2

    
    for i in range(3, N+1, 2):
        if (prime[i] == False):

            s[i] = i

            for j in range(i, int(N / i) + 1, 2):
                if (prime[i*j] == False):
                    prime[i*j] = True

                    
                    s[i * j] = i


def generatePrimeFactors(N):

    s = [0] * (N+1)

    sieveOfEratosthenes(N, s)


    curr = s[N]

    # Power of current prime factor
    cnt = 1
    ans=1


    while (N > 1):
        N //= s[N]

        # power
        if (curr == s[N]):
            cnt += 1
            continue

        ans*=(1+cnt)

        curr = s[N]
        cnt = 1
    return ans


N = int(input())
sumi=0
for i in range(1,N):
    sumi+=generatePrimeFactors(N-i)
print(sumi)


### FIXED CODE ###

ans=0
n=int(input())
for i in range(1,n):
  ans+=(n-1)//i
print(ans)
### BUGGY CODE ###

h,w,n=map(int,input().split())
d={}
for _ in range(n):
    a,b=map(int,input().split()) 
    for i in (-1,0,1):
        for j in (-1,0,1):
            if 2<=a+i<=h-1 and 2<=b+j<=w-1:
                d.setdefault((a+i,b+j),0)
                d[a+i,b+j]+=1
r=[0]*10
for i in d.values():
    r[i]+=1
r[0]=(h-2)*(w-2)-sum(r)
for i in r:
    print(i)

### FIXED CODE ###

h,w,n=map(int,input().split())
d={}
for _ in range(n):
    a,b=map(int,input().split()) 
    for i in (-1,0,1):
        for j in (-1,0,1):
            if 2<=a+i<=h-1 and 2<=b+j<=w-1:
                d.setdefault((a+i,b+j),0)
                d[a+i,b+j]+=1
r=[0]*10
for i in d.values():
    r[i]+=1
r[0]=(h-2)*(w-2)-sum(r)
for i in r:
    print(i)
### BUGGY CODE ###

n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for a, b in AB:
  e[a].append(b)
  e[b].append(a)
  
color = {}
for a, b in AB:
  color[(a, b)] = -1
  color[(b, a)] = -1
cidx = max([len(i) for i in e])

for itr, i in enumerate(e):
  cls = set(range(1, cidx + 1))
  cls -= set([color[(itr, k)] for k in i])
  for j in i:
    if color[(itr,j)] == -1 or color[(j,itr)] == -1:
      cl = cls.pop()
      color[(itr, j)] = cl 
      color[(j, itr)] = cl
      
print(cidx)
for i in AB:
  print(color[i])

### FIXED CODE ###

from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append((b, itr))
  e[b].append((a, itr))
  
cidx = max([len(i) for i in e])

ans = [-1] * (n - 1)

q = deque()
q.append((0, 0, -1))
# 色は１から順に塗っていく
while q:
  v, p, pcol = q.popleft()
  col = 1
  for u, i in e[v]:
    if u != p:
      # 親と色がかぶる時は＋１
      if col == pcol:
        col += 1
      if ans[i] == -1: 
        ans[i] = col
      q.append((u, v, col))
      col += 1 

print(cidx)
for i in ans:
  print(i)
### BUGGY CODE ###

#input = raw_input
#import numpy as np

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

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    new_elms = sorted(values[i], reverse=True)[:M-i+1]
    elms += new_elms
    if len(elms) >= 1:
        max_val = max(elms)
        out += max_val
        elms.remove(max_val)

print(out)

### FIXED CODE ###

#input = raw_input
#import numpy as np

from heapq import heappush, heappop

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

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(-B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    #print("values[i]", values[i])
    for elm in values[i]:
        heappush(elms, elm)
        
    if len(elms) >= 1:
        max_val = - heappop(elms)
        #print("mval", max_val)
        out += max_val

print(out)
### BUGGY CODE ###

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

ans_list = {}

for i in range(N):
    for j in range(i+1, N):
        if not S[j + 1:N] or S[i] + S[j] in S_set:
            continue
        ans_list[S[i] + S[j]] = S[j + 1:N]
        S_set.add(S[i] + S[j])
count = 0
# print(ans_list)
ans_len_list = [len(set(value)) for value in ans_list.values()]
print(sum(ans_len_list))

### FIXED CODE ###

N = int(input())
S = list(input())
visited = {}

count = 0

for i, s in enumerate(S):
    if s in visited:
        continue
    visited[s] = []
    for j, s2 in enumerate(S[i+1:N-1]):
        # print(s, s2, S[i + j + 2:N])
        if s2 in visited[s]:
            continue
        count += len(set(S[i + j + 2:N]))
        visited[s].append(s2)
        # print(s, s2, set(S[j + 1:N]))
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
tmp = 0
for i in range(len(a)):
         tmp += a[i]
         if tmp >= (sum(a))//2:
                  break
print(min((abs((sum(a)-tmp)-tmp)),abs((sum(a)-(tmp-a[i]))-(tmp-a[i]))))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
suma = sum(a)
tmp = 0
for i in range(len(a)):
         tmp += a[i]
         if tmp >= suma//2:
                  break
print(min((abs((suma-tmp)-tmp)),abs((suma-(tmp-a[i]))-(tmp-a[i]))))
### BUGGY CODE ###

from collections import deque
x,y,a,b,c = map(int,input().split())

p = deque(sorted(list(map(int,input().split()))))
q = deque(sorted(list(map(int,input().split()))))
r = deque(sorted(list(map(int,input().split()))))

ans = deque(maxlen=(x+y))

def insertion(z):
	global x,y
	if z == p:
		x -= 1
	else:
		y -= 1
	return ans.append(z.pop())

while x > 0 or y > 0:
	if x and y:
		if p[-1] > q[-1] :
			insertion(p)
		else:
			insertion(q)
	elif not x:
		insertion(q)
	else:
		insertion(p)

while r:
	if ans[-1] < r[-1]:
		ans.appendleft(r.pop())

print(sum(ans))



### FIXED CODE ###

from collections import deque
x,y,a,b,c = map(int,input().split())

p = deque(sorted(list(map(int,input().split()))))
q = deque(sorted(list(map(int,input().split()))))
r = deque(sorted(list(map(int,input().split()))))

ans = deque(maxlen=(x+y))

def insertion(z):
	global x,y
	if z == p:
		x -= 1
	else:
		y -= 1
	return ans.append(z.pop())

while x > 0 or y > 0:
	if x and y:
		if p[-1] > q[-1] :
			insertion(p)
		else:
			insertion(q)
	elif not x:
		insertion(q)
	else:
		insertion(p)

while r:
	if ans[-1] < r[-1]:
		ans.appendleft(r.pop())
	else:
		break

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

import bisect

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()

    for i in range(M):
        a = A.pop()
        a = a // 2
        bisect.insort_right(A, a)

    # print(A)
    x = sum(A)
    print(x)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = [-1 * i for i in A]

    heapq.heapify(A)

    for i in range(M):
        a = heapq.heappop(A)
        a = -1 * (-1 * a // 2)
        heapq.heappush(A, a)


    x = -1 * sum(A)
    print(x)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
x = list(map(int, input().split()))
count=0

for i in range(N):
    if x[i]==1:
        count=count+1
        break
    elif x[i]==min(x[0:i+1]):
        count=count+1
print(count)


### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
count=0
min=2000000
for i in range(N):
    if min>=x[i]:
        count=count+1
        min=x[i]
print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(m)]

ans = set(range(lr[0][1] + 1)) - set(range(lr[0][0]))
for l, r in lr:
    ans &= (set(range(r + 1)) - set(range(l)))
print(len(ans) if n > len(ans) else n)

### FIXED CODE ###

n, m = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(m)]

max_l = float("-inf")
min_r = float("inf")

for l, r in lr:
    max_l = max(max_l, l)
    min_r = min(min_r, r + 1)

ans = min_r-max_l
print("0" if ans <= 0 else ans if ans < n else n)
### BUGGY CODE ###

N = int(input())
s = []
for i in range(N):
    p = list(input())
    p.sort()
    q = "".join(p)
    s.append(q)


cnt = 0
for i in range(N-1):
    cnt += s[i+1:].count(s[i])


print(cnt)
        


### FIXED CODE ###

N = int(input())
s = []
for i in range(N):
    p = list(input())
    p.sort()
    q = "".join(p)
    s.append(q)

cnt = 0
s = sorted(s)
seq = 1
prek = s[0] 
for k in range(1, N):
    if prek == s[k]:
        seq += 1
    else:
        cnt += seq*(seq-1)/2
        seq = 1

    prek = s[k]

cnt += seq*(seq-1)/2


print(int(cnt))
### BUGGY CODE ###

def solve(N, M, lrd):
    vs = {}
    def calc(l, r):
        cs = set([l])
        xs = [(l, 0)]
        while xs:
            x = xs.pop()
            if x[0] in vs:
                for y, d in vs[x[0]].items():
                    if y == r:
                        return d + x[1]
                    if y not in cs: 
                        xs.append((y, d + x[1]))
                        cs.add(y)
        return None
    for l, r, d in lrd:
        x = calc(l, r)
        if not x is None and x != d:
            return False
        if l not in vs:
            vs[l] = {}
        if r not in vs:
            vs[r] = {}
        vs[l][r] = d
        vs[r][l] = -d
    return True

if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    lrd = []
    for i in range(M):
        lrd.append([int(x) for x in input().split()])
    if solve(N, M, lrd):
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

def solve(N, M, lrd):
    edges = {}
    nodes = {}
    for l, r, d in lrd:
        if not l in edges:
            edges[l] = {}
        if not r in edges:
            edges[r] = {}
        edges[l][r] = d
        edges[r][l] = -d
        nodes[l] = None
        nodes[r] = None
    for node in nodes:
        if nodes[node] is not None:
            continue
        nodes[node] = 0
        stack = []
        stack.append(node)
        while stack:
            node = stack.pop()
            for n, d in edges[node].items():
                if nodes[n] is None:
                    stack.append(n)
                    nodes[n] = nodes[node] + edges[node][n]
                else:
                    if nodes[n] != nodes[node] + edges[node][n]:
                        return False
    return True

if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    lrd = []
    for i in range(M):
        lrd.append([int(x) for x in input().split()])
    if solve(N, M, lrd):
        print("Yes")
    else:
        print("No")