Eulerian Circuit in an Undirected Graph

An Eulerian Circuit in an undirected graph is a closed path that uses every edge exactly once and returns to the starting vertex. A necessary and sufficient condition for an undirected graph to have an Eulerian Circuit is that every vertex with a nonzero degree is connected within a single connected component, and each vertex has an even degree. In other words, for every vertex \(v\), the degree \(d(v)\) must satisfy \(d(v) \equiv 0 \pmod{2}\).

Your task is to determine whether a given undirected graph contains an Eulerian Circuit. The graph is described by its number of vertices and edges, along with a list of edges.

Note: If the graph contains no edges (i.e. \(m = 0\)), then the graph is considered to have an Eulerian Circuit only if there is exactly one vertex.

inputFormat

The input is given via standard input (stdin) and has the following format:

 n m
 u1 v1
 u2 v2
 ...
 um vm

Where:

• \(n\) is the number of vertices.
• \(m\) is the number of edges.
• Each of the next \(m\) lines contains two integers \(u\) and \(v\), representing an undirected edge between vertices \(u\) and \(v\).

outputFormat

The output should be a single line to standard output (stdout) containing either YES if the graph contains an Eulerian Circuit, or NO otherwise.

3 3
1 2
2 3
3 1

YES