Bipartite Graph - Classic Problems | Repovive

CLS30. Bipartite Graph

1s256 MB

Given an undirected graph with $n$ vertices and $m$ edges, determine if it is bipartite.

A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. Equivalently, a graph is bipartite if and only if it contains no odd-length cycle.

Output YES if the graph is bipartite, otherwise output NO.

Constraints

$1 \le n \le 10^5$
$0 \le m \le 10^5$
No self-loops

Input

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

Output

$\texttt{YES} \text{ or } \texttt{NO}$

Samples

Input

Explanation

For this input, the required output is YES.

Output

YES

Input

Explanation

For this input, the required output is NO.

Output

NO

Input

4 2
1 2
3 4

Explanation

For this input, the required output is YES.

Output

YES

Given an undirected graph with $n$ vertices and $m$ edges, determine if it is bipartite.

Output YES if the graph is bipartite, otherwise output NO.

$1 \le n \le 10^5$
$0 \le m \le 10^5$
No self-loops

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

$\texttt{YES} \text{ or } \texttt{NO}$