CodeEff/ECCO huggingface dataset:
# Original solution
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))
edges = [list(range(N)) for i in range(N)]
for i in range(N):
    edges[i].remove(i)
for _ in range(M):
    a, b = list(map(int, input().split()))
    edges[a-1].remove(b-1)
    edges[b-1].remove(a-1)
size = defaultdict(lambda: [0, 0])
color = [-1]*N
def set_color(root):
    
    que = deque([root])
    color[root] = 0
    size[root][0]+=1
    while que:
        v = que.pop()
        for nv in edges[v]:
            if color[nv]<0:
                c = 1- color[v]
                color[nv] = c
                size[root][c]+=1
                que.append(nv)
            elif color[nv] == color[v]:
                print((-1))
                sys.exit()
for i in range(N):
    if color[i]<0:
        set_color(i)
S = set([0])
for a, b in list(size.values()):
    S = set(s+b for s in S)|set(s+a for s in S)
ans = min(x*(x-1)//2+(N-x)*(N-x-1)//2 for x in S)            
print(ans)                

# Optimized solution
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))
edges = [set(range(N)) for i in range(N)]
for i in range(N):
    edges[i].remove(i)
for _ in range(M):
    a, b = list(map(int, input().split()))
    edges[a-1].remove(b-1)
    edges[b-1].remove(a-1)
size = defaultdict(lambda: [0, 0])
color = [-1]*N
def set_color(root):
    
    que = deque([root])
    color[root] = 0
    size[root][0]+=1
    while que:
        v = que.pop()
        for nv in edges[v]:
            if color[nv]<0:
                c = 1- color[v]
                color[nv] = c
                size[root][c]+=1
                que.append(nv)
            elif color[nv] == color[v]:
                print((-1))
                sys.exit()
for i in range(N):
    if color[i]<0:
        set_color(i)
S = set([0])
for a, b in list(size.values()):
    S = set(s+b for s in S)|set(s+a for s in S)
ans = min(x*(x-1)//2+(N-x)*(N-x-1)//2 for x in S)            
print(ans)
# Original solution
from itertools import product


def dfs(links, fixed, s):
    q = [(s, 0)]
    cnt = [0, 0]
    while q:
        v, c = q.pop()
        if fixed[v] > -1:
            if fixed[v] != c:
                return False
            continue
        fixed[v] = c
        cnt[c] += 1
        for u in links[v]:
            q.append((u, c ^ 1))
    return cnt


def is_bipartite(n, links):
    fixed = [-1] * n
    can = []
    for i in range(n):
        if fixed[i] > -1:
            continue
        cnt = dfs(links, fixed, i)
        if cnt == False:
            return -1
        can.append(cnt)
    mx = float('inf')
    for p in product(*can):
        s = sum(p)
        t = n - s
        tmx = max(s, t)
        mx = min(mx, tmx)

    mn = n - mx
    return (mx * (mx - 1) + mn * (mn - 1)) // 2


n, m = list(map(int, input().split()))
links = [set(range(n)) - {i} for i in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    links[a].remove(b)
    links[b].remove(a)
print((is_bipartite(n, links)))


# Optimized solution
def dfs(links, fixed, s):
    q = [(s, 0)]
    cnt = [0, 0]
    while q:
        v, c = q.pop()
        if fixed[v] > -1:
            if fixed[v] != c:
                return False
            continue
        fixed[v] = c
        cnt[c] += 1
        for u in links[v]:
            q.append((u, c ^ 1))
    return (max(cnt), min(cnt))


def is_bipartite(n, links):
    fixed = [-1] * n
    l, r = 0, 0
    can = []
    for i in range(n):
        if fixed[i] > -1:
            continue
        cnt = dfs(links, fixed, i)
        if cnt == False:
            return -1
        can.append(cnt)

    can.sort(reverse=True)
    for cnt in can:
        j = 0 if cnt[0] > cnt[1] else 1
        if l > r:
            j ^= 1
        l += cnt[j]
        r += cnt[j ^ 1]
    return (l * (l - 1) + r * (r - 1)) // 2


n, m = list(map(int, input().split()))
links = [set(range(n)) - {i} for i in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    links[a].remove(b)
    links[b].remove(a)
print((is_bipartite(n, links)))
# Original solution
N, M = list(map(int, input().split()))
E = [[] for _ in range(N+1)]
E_mat = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    E[a].append(b)
    E[b].append(a)
    E_mat[a][b] = 1
    E_mat[b][a] = 1
E_inv = [[] for _ in range(N+1)]
for v, e_mat in enumerate(E_mat[1:], 1):
    for u, e in enumerate(e_mat[1:], 1):
        if e==0 and v!=u:
            E_inv[v].append(u)
colors = [0] * (N+1)
def dfs(v, c):
    colors[v] = c
    cnts[c] += 1
    for u in E_inv[v]:
        if colors[u] == c:
            print((-1))
            exit()
        if colors[u] != 0:
            continue
        dfs(u, -c)
K = []
for v in range(1, N+1):
    cnts = [0, 0, 0]
    if colors[v] == 0:
        dfs(v, 1)
    K.append(cnts[1:])

dp = 1
for a, b in K:
    dp = dp<<a | dp<<b

dp = bin(dp)[:1:-1]
ans = 0
mi = float("inf")
for i, c in enumerate(dp):
    if c=="1":
        if mi > abs(N/2-i):
            mi = abs(N/2-i)
            ans = i

print((ans*(ans-1)//2 + (N-ans)*(N-ans-1)//2))


# Optimized solution
def main():
    N, M = list(map(int, input().split()))
    E_mat = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        a, b = list(map(int, input().split()))
        E_mat[a][b] = 1
        E_mat[b][a] = 1
    E_inv = [[] for _ in range(N+1)]
    for v, e_mat in enumerate(E_mat[1:], 1):
        for u, e in enumerate(e_mat[1:], 1):
            if e==0 and v!=u:
                E_inv[v].append(u)
    colors = [0] * (N+1)
    
    def dfs(v, c):
        colors[v] = c
        cnts[c] += 1
        for u in E_inv[v]:
            if colors[u] == c:
                print((-1))
                exit()
            if colors[u] != 0:
                continue
            dfs(u, -c)
            
    K = []
    for v in range(1, N+1):
        cnts = [0, 0, 0]
        if colors[v] == 0:
            dfs(v, 1)
        K.append(cnts[1:])
    
    dp = 1
    for a, b in K:
        dp = dp<<a | dp<<b
    
    dp = bin(dp)[:1:-1]
    ans = 0
    mi = float("inf")
    for i, c in enumerate(dp):
        if c=="1":
            if mi > abs(N/2-i):
                mi = abs(N/2-i)
                ans = i
    
    print((ans*(ans-1)//2 + (N-ans)*(N-ans-1)//2))

main()
# Original solution
N,M=list(map(int,input().split()))
edge=[set([]) for i in range(N)]
for i in range(M):
    a,b=list(map(int,input().split()))
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

cedge=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if j not in edge[i] and j!=i:
            cedge[i].append(j)

ans=[]
def is_bipartgraph():
    color=[0]*N
    used=[False]*N
    for i in range(N):
        if not used[i]:
            stack=[(i,1)]
            black=0
            white=0
            while stack:
                v,c=stack.pop()
                color[v]=c
                black+=(not used[v])*(c==1)
                white+=(not used[v])*(c==-1)
                used[v]=True
                for nv in cedge[v]:
                    if color[nv]==color[v]:
                        return False
                    elif color[nv]==0:
                        stack.append((nv,-c))
            ans.append([black,white])
    return True

if is_bipartgraph():
    dp=[[False for i in range(0,N+1)] for j in range(len(ans))]
    a,b=ans[0]
    dp[0][a],dp[0][b]=True,True
    for i in range(1,len(ans)):
        a,b=ans[i]
        for j in range(0,N+1):
            test=False
            if j>=a:
                test=test|dp[i-1][j-a]
            if j>=b:
                test=test|dp[i-1][j-b]
            dp[i][j]=test
    ans=0
    for i in range(0,N+1):
        if dp[-1][i] and abs(ans-N/2)>abs(i-N/2):
            ans=i
    ans2=N-ans
    print((ans*(ans-1)//2+ans2*(ans2-1)//2))
else:
    print((-1))


# Optimized solution
N,M=list(map(int,input().split()))
edge=[set([]) for i in range(N)]
for i in range(M):
    a,b=list(map(int,input().split()))
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

cedge=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if j not in edge[i] and j!=i:
            cedge[i].append(j)

ans=[]
def is_bipartgraph():
    color=[0]*N
    used=[False]*N
    for i in range(N):
        if not used[i]:
            stack=[(i,1)]
            black=0
            white=0
            while stack:
                v,c=stack.pop()
                if not used[v]:
                    color[v]=c
                    black+=(c==1)
                    white+=(c==-1)
                    used[v]=True
                    for nv in cedge[v]:
                        if color[nv]==color[v]:
                            return False
                        elif color[nv]==0:
                            stack.append((nv,-c))
            ans.append([black,white])
    return True

if is_bipartgraph():
    dp=[[False for i in range(0,N+1)] for j in range(len(ans))]
    a,b=ans[0]
    dp[0][a],dp[0][b]=True,True
    for i in range(1,len(ans)):
        a,b=ans[i]
        for j in range(0,N+1):
            test=False
            if j>=a:
                test=test|dp[i-1][j-a]
            if j>=b:
                test=test|dp[i-1][j-b]
            dp[i][j]=test
    ans=0
    for i in range(0,N+1):
        if dp[-1][i] and abs(ans-N/2)>abs(i-N/2):
            ans=i
    ans2=N-ans
    print((ans*(ans-1)//2+ans2*(ans2-1)//2))
else:
    print((-1))
# Original solution
n,m=list(map(int,input().split()))
a=[False]*n
g=[[] for _ in [0]*n]
for _ in range(m):
    l,r,d=list(map(int,input().split()))
    g[l-1].append((r-1,d))
    g[r-1].append((l-1,-d))
for i in range(n):
    if not(a[i]):
        a[i]=0
        q=[i]
    while q:
        j=q.pop()
        for x,e in g[j]:
            if not(a[x]):
                a[x]=a[j]+e
                q.append(x)
            elif a[x]!=a[j]+e:
                print("No")
                exit()
                
print("Yes")


# Optimized solution
n,m=list(map(int,input().split()))
a=[None]*n
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=list(map(int,input().split()))
    g[l-1].append((r-1,d))
    g[r-1].append((l-1,-d))
for i in range(n):
    if a[i]==None:
        a[i]=0
        q=[i]
    while q:
        j=q.pop()
        for x,e in g[j]:
            if a[x]==None:
                a[x]=a[j]+e
                q.append(x)
            elif a[x]!=a[j]+e:
                print("No")
                exit()
                
print("Yes")
# Original solution
class WeightedUnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.weight = [0 for _ in range(n)]
    def find(self,x):
        root = x
        stack = [root]
        while self.parents[root] != root:
            root = self.parents[root]
            stack.append(root)
        while stack:
            s = stack.pop()
            self.weight[s] += self.weight[self.parents[s]]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root
    def unite(self,x,y,w):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.weight[xroot] = w-self.weight[x]+self.weight[y]
        else:
            self.parents[yroot] = xroot
            self.weight[yroot] = -w+self.weight[x]-self.weight[y]
            if xrank == yrank:
                self.rank[xroot] += 1
    def diff(self,x,y):
        return self.weight[x]-self.weight[y]

N,M = list(map(int,input().split()))
uf = WeightedUnionFind(N)

for _ in range(M):
    l,r,d = list(map(int,input().split()))
    if uf.find(l-1) == uf.find(r-1):
        if uf.diff(l-1,r-1) != d:
            print('No')
            break
    else:
        uf.unite(l-1,r-1,d)
else:
    print('Yes')

# Optimized solution
class DSUWeighted():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n
        self.wt = [0] * n

    def leader(self, a):
        #assert 0 <= a < self.n
        x = a
        order = [x]
        while self.par_size[x] >= 0:
            x = self.par_size[x]
            order.append(x)
        for s in order[:-1][::-1]:
            self.wt[s] += self.wt[self.par_size[s]]
            self.par_size[s] = x
        return x

    def same(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def merge(self, a, b, w):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        w += self.wt[a] - self.wt[b]
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]:
            x, y = y, x
            w = -w
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        self.wt[y] = w
        return x

    def diff(self, x, y):
        return self.wt[y] - self.wt[x]

import sys
input = sys.stdin.buffer.readline

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

uf = DSUWeighted(N)

for _ in range(M):
    l, r, d = list(map(int, input().split()))
    if uf.same(l - 1, r - 1):
        if uf.diff(l - 1, r - 1) != d:
            print('No')
            break
    else:
        uf.merge(l - 1, r - 1, d)
else:
    print('Yes')
# Original solution
#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)
  
n,m = [int(i) for i in input().split()]
par = [-1]*n
wei = [0]*n

for i in range(m):
  l,r,d = [int(i) for i in input().split()]
  if not same(l-1,r-1):
    unite(l-1,r-1,d)
  else:
    if diff(l-1,r-1) == d:
      continue
    else:
      print('No')
      exit()

print('Yes')

# Optimized solution
#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)
  
import sys
input = sys.stdin.readline  
n,m = [int(i) for i in input().split()]
par = [-1]*n
wei = [0]*n

for i in range(m):
  l,r,d = [int(i) for i in input().split()]
  if not same(l-1,r-1):
    unite(l-1,r-1,d)
  else:
    if diff(l-1,r-1) == d:
      continue
    else:
      print('No')
      exit()

print('Yes')
# Original solution
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = list(map(int, sys.stdin.readline().split()))
    lrds = tuple(tuple(map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    for i in range(n):
        if x[i]:
            continue
        stack = [i]
        x[i] = 0
        while len(stack):
            v = stack.pop()
            for u, d in g[v]:
                if not x[u]:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = list(map(int, sys.stdin.readline().split()))
    lrds = ((list(map(int, line.split()))) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    for i in range(n):
        if x[i] is not None:
            continue
        stack = [i]
        x[i] = 0
        while len(stack):
            v = stack.pop()
            for u, d in g[v]:
                if x[u] is None:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

if __name__ == '__main__':
    main()
# Original solution
from collections import deque

n, m = list(map(int, input().split()))
graph = [[] for _ in range(n)]
for i in range(m):
    l, r, d = list(map(int, input().split()))
    l -= 1
    r -= 1
    graph[r].append((l, i, -d))
    graph[l].append((r, i, d))

check_v = [False for _ in range(n)]
check_e = [False for _ in range(m)]
max_int = 10 ** 10
point = [max_int for _ in range(n)]

for v in range(n):
    Q = deque()
    if not check_v[v]:
        Q.append(v)
    while Q:
        v = Q.popleft()
        for next_v, e, d in graph[v]:                
            if not check_e[e]:
                if point[v] == max_int:
                    point[v] = 0
                if point[next_v] == max_int:
                    point[next_v] = point[v] + d
                else:
                    if point[next_v] != point[v] + d:
                        print('No')
                        exit()
            check_e[e] = True
            if not check_v[next_v]:
                Q.append(next_v)
            check_v[v] = True
print('Yes')


# Optimized solution
from collections import deque

n, m = list(map(int, input().split()))
graph = [[] for _ in range(n)]
for i in range(m):
    l, r, d = list(map(int, input().split()))
    l -= 1
    r -= 1
    graph[r].append((l, r, -d))
    graph[l].append((r, l, d))

max_int = 10 ** 10
point = [None for _ in range(n)]

for v in range(n):
    Q = deque()
    if point[v] is not None:
        continue
    Q.extend(graph[v])
    while Q:
        next_v, v, d = Q.popleft()
        if point[v] is None:
            point[v] = 0
        if point[next_v] is not None:
            if point[next_v] != point[v] + d:
                print('No')
                exit()
            else:
                continue
        point[next_v] = point[v] + d
        Q.extend(graph[next_v])
print('Yes')
# Original solution
def topo_sort(g):
    from collections import deque
    V = len(g)
    deg = [0]*V
    for src in range(V):
        for dst in g[src]:
            deg[dst] += 1
    ans = list(v for v in range(V) if deg[v]==0)
    deq = deque(ans)
    used = [0]*V

    while deq:
        v = deq.popleft()
        for t in g[v]:
            deg[t] -= 1
            if deg[t]==0:
                deq.append(t)
                ans.append(t)
    return ans

def resolve():
    N, M = list(map(int, input().split()))
    LRD = [list(map(int, input().split())) for _ in range(M)]
    adj_list = [[] for _ in range(N)]
    adj_matrix = [[None for _ in range(N)] for __ in range(N)]
    for lrd in LRD:
        l, r, d = lrd
        adj_list[l-1].append(r-1)
        adj_matrix[l-1][r-1] = d
    
    #top_order = topological_sort(adj_list)
    top_order = topo_sort(adj_list)
    
    if len(top_order) != len(adj_list):
        print("No")
        return
    
    acc = 0
    start = top_order[0]
    now = top_order[0]
    for i in range(1, len(top_order)):
        nxt = top_order[i]
        if adj_matrix[now][nxt] is not None:
            if adj_matrix[start][nxt] is not None and acc+adj_matrix[now][nxt] != adj_matrix[start][nxt]:
                print("No")
                return
            acc += adj_matrix[now][nxt]
        now = nxt
        
    print("Yes")


if '__main__' == __name__:
    resolve()

# Optimized solution
def resolve():
    N, M = list(map(int, input().split()))
    LRD = [list(map(int, input().split())) for _ in range(M)]
    adj_list = [[] for _ in range(N)]
    for lrd in LRD:
        l, r, d = lrd
        adj_list[l-1].append((l-1, r-1, d))
        adj_list[r-1].append((r-1, l-1, -d))
    
    X = [None]*N
    import collections

    for i in range(N):
        if X[i] is not None:
            continue
        q = collections.deque(adj_list[i])
        X[i] = 0
        while q:
            src, nxt, d = q.pop()
            if X[nxt] is not None:
                if X[nxt] != X[src] + d:
                    print("No")
                    return
            else:
                X[nxt] = X[src] + d
                q.extend(adj_list[nxt])
    print("Yes")

    


if '__main__' == __name__:
    resolve()
# Original solution
import collections
def main():
    N, M = list(map(int, input().split()))
    graph = collections.defaultdict(dict)
    for _ in range(M):
        L, R, D = list(map(int, input().split()))
        graph[L][R] = D
        graph[R][L] = -D

    visited = set()
    for i in range(1, N+1):
        if i not in visited:
            cur = dict()
            cur[i] = 0
            while True:
                temp = dict()
                for j in cur:
                    for k in graph[j]:
                        l = cur[j] + graph[j][k]
                        if k not in cur:
                            temp[k] = l
                        elif k in cur and cur[k] != l:
                            return "No"
                        elif k in temp and temp[k] != l:
                            return "No"
                for k in temp:
                    cur[k] = temp[k]
                if len(temp) == 0:
                    break
    return "Yes"

if __name__ == '__main__':
    print((main()))

# Optimized solution
import collections
def main():
    N, M = list(map(int, input().split()))
    graph = collections.defaultdict(dict)
    for _ in range(M):
        L, R, D = list(map(int, input().split()))
        graph[L][R] = D
        graph[R][L] = -D

    visited = set()
    used = set()
    for i in range(1, N+1):
        if i not in visited:
            dist = dict()
            dist[i] = 0
            cur = [i]
            visited.add(i)
            while cur:
                temp = []
                for j in cur:
                    for k in graph[j]:
                        if (j, k) not in used and (k, j) not in used:
                            used.add((j, k))
                            used.add((k, j))
                            if k not in dist:
                                dist[k] = dist[j] + graph[j][k]
                                temp.append(k)
                                visited.add(k)
                            elif k in dist:
                                if dist[k] != dist[j] + graph[j][k]:
                                    return "No"
                cur = temp

    return "Yes"

if __name__ == '__main__':
    print((main()))