from collections import defaultdict import sys readline=sys.stdin.readline read=sys.stdin.read class Graph: def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")): self.V=V self.directed=directed self.weighted=weighted self.inf=inf if not graph: self.edges=edges self.graph=[[] for i in range(self.V)] if weighted: for i,j,d in self.edges: self.graph[i].append((j,d)) if not self.directed: self.graph[j].append((i,d)) else: for i,j in self.edges: self.graph[i].append(j) if not self.directed: self.graph[j].append(i) else: self.graph=graph self.edges=[] for i in range(self.V): if self.weighted: for j,d in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j,d)) else: for j in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j)) def Euler_Path(self,s=None,t=None): if self.directed: indegree=[0]*self.V outdegree=[0]*self.V graph=[[] for x in range(self.V)] for tpl in self.edges: if self.weighted: u,v,d=tpl else: u,v=tpl indegree[v]+=1 outdegree[u]+=1 graph[v].append(u) for x in range(self.V): if indegree[x]+1==outdegree[x]: if s==None: s=x elif s!=x: return False elif indegree[x]==outdegree[x]+1: if t==None: t=x elif t!=x: return False elif indegree[x]!=outdegree[x]: return False if (s,t)==(None,None): for x in range(self.V): if graph[x]: s=x t=x break elif s==None: s=t elif t==None: t=s elif s==t: for x in range(self.V): if indegree[x]!=outdegree[x]: return False queue=[t] euler_path=[] while queue: while graph[queue[-1]]: queue.append(graph[queue[-1]].pop()) x=queue.pop() euler_path.append(x) for x in range(self.V): if graph[x]: return False else: degree=[0]*self.V graph=[[] for x in range(self.V)] use_count=[defaultdict(int) for x in range(self.V)] for tpl in self.edges: if self.weighted: u,v,d=tpl else: u,v=tpl degree[v]+=1 degree[u]+=1 graph[u].append(v) graph[v].append(u) for x in range(self.V): if degree[x]%2: if s==None and t!=x: s=x elif t==None and s!=x: t=x elif not x in (s,t): return False if s==None and t==None: for x in range(self.V): if graph[x]: s=x t=x break else: s,t=0,0 elif s==None: s=t elif t==None: t=s elif s!=t: if degree[s]%2==0 or degree[t]%2==0: return False queue=[t] euler_path=[] while queue: while graph[queue[-1]]: if use_count[queue[-1]][graph[queue[-1]][-1]]: use_count[queue[-1]][graph[queue[-1]][-1]]-=1 graph[queue[-1]].pop() else: queue.append(graph[queue[-1]].pop()) use_count[queue[-1]][queue[-2]]+=1 x=queue.pop() euler_path.append(x) for x in range(self.V): if graph[x]: return False if euler_path[0]!=s: return False return euler_path N,M=map(int,readline().split()) edges=[] for _ in range(M): a,b=map(int,readline().split()) edges.append((a,b)) G=Graph(N,edges=edges) path=G.Euler_Path() if path: ans="YES" else: ans="NG" print(ans)