Bipartite Graph Check

Given an undirected graph \(G = (V, E)\) with \(N\) vertices and \(M\) edges, determine whether the graph is bipartite.

A graph is considered bipartite if its vertex set \(V\) can be partitioned into two disjoint sets \(V_1\) and \(V_2\) such that every edge \((u, v) \in E\) satisfies either \(u \in V_1, v \in V_2\) or \(u \in V_2, v \in V_1\). In other words, the graph can be 2-colored so that no two adjacent vertices share the same color.

This problem can be solved using a BFS or DFS approach. Here, we use BFS to assign colors alternately. If a conflict arises during coloring (i.e. two adjacent vertices receive the same color), the graph is not bipartite.

inputFormat

The input is given via standard input (stdin).

The first line contains two integers (N) and (M), representing the number of vertices and edges, respectively. Each of the following (M) lines contains two integers (u) and (v), which denote an undirected edge between vertices (u) and (v).

outputFormat

Output via standard output (stdout) a single line containing either "YES" if the graph is bipartite or "NO" if it is not.## sample

3 3
1 2
1 3
2 3

NO