Bipartite Graph Check

You are given an undirected graph. Your task is to determine whether the graph is bipartite or not. A graph is bipartite if its vertex set can be partitioned into two disjoint subsets such that for every edge \( (u,v) \), the vertices \( u \) and \( v \) belong to different subsets. In other words, the condition can be written as: $$\forall (u,v) \in E,\; color(u)\neq color(v).$$

The graph might be disconnected and can include self-loops. A self-loop (an edge from a vertex to itself) is not allowed in a bipartite graph.

inputFormat

The input is read from standard input (stdin) and has the following format:

N M
u1 v1
... 
uM vM

Where:

• N is the number of vertices (vertices are numbered from 1 to N).
• M is the number of edges.
• Each of the following M lines contains two integers u and v representing an edge between vertices u and v.

outputFormat

Output to standard output (stdout) a single line containing YES if the graph is bipartite, and NO otherwise.

4 4
1 2
2 3
3 4
4 1

YES