Bipartite Graph Checker

You are given an undirected graph with n vertices and m edges. The task is to determine whether the graph is bipartite.

A graph is bipartite if the set of vertices can be divided into two disjoint subsets such that no two vertices within the same subset are adjacent. Equivalently, a graph is bipartite if it does not contain an odd-length cycle.

Input Format: The first line contains two integers n and m, the number of vertices and edges, respectively. The next m lines each contain two integers u and v, indicating that there is an edge between vertices u and v.

Output Format: Output a single line containing "YES" if the graph is bipartite, or "NO" otherwise.

The bipartite property can be formally stated as: For every edge between vertices u and v, if we assign one of two colors to u and v, then u and v must have different colors. In terms of graph theory, this means the graph does not contain any odd cycle, i.e., a cycle with an odd number of edges.

Mathematically, if we denote the two colors as 0 and 1 then for any edge \( (u,v) \), we require:

\[ color(u) \neq color(v) \]

inputFormat

The first line contains two integers n (number of vertices) and m (number of edges).

The following m lines each contain two integers u and v representing an edge between vertices u and v.

You can assume that the vertices are labeled from 1 to n.

outputFormat

Output a single line: "YES" if the graph is bipartite, otherwise "NO".

## sample

4 4
1 2
2 3
3 4
4 1

YES