Is the Graph Always List 2-Colorable?

Pupil loves to color the vertices of a graph. One day, Master decided to challenge him by giving him an undirected graph with no multiple edges or self-loops. In addition, for each vertex, Master assigns a set of 2 available colors. Pupil must choose one color from the given set for each vertex such that no two adjacent vertices share the same color.

The twist is that Master may choose any two‐color list for each vertex. Pupil wonders: regardless of how Master assigns the color sets, is it always possible to obtain a proper coloring? In other words, is the graph list 2‑colorable for every possible assignment of color lists?

Note: A graph is list 2‑colorable if and only if every connected component is bipartite and contains at most one cycle. Equivalently, each connected component must be either a tree (acyclic) or an even cycle (or a combination of trees and a single even cycle in that component). If any component has more than one cycle, then there exists some assignment of lists that prevents a proper coloring.

Your task is to determine, given an undirected graph, whether no matter how the two‐color lists are assigned to each vertex, there is always a valid coloring.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵), where n is the number of vertices and m is the number of edges.

Each of the following m lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) indicating that there is an undirected edge between vertices u and v. There are no multiple edges or self-loops.

outputFormat

Output a single line containing YES if for every possible assignment of two colors per vertex there exists a proper vertex-coloring. Otherwise, output NO.

sample

3 2
1 2
2 3

YES