Problem C. Bipartite graph

Author:StdAlg (adapted by T. Chistyakov, A. Klenin)   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

For a given undirected graph with N vertices and M edges you need to figure out whether the graph is bipartite or no.

NOTE. A graph is called bipartite if it's possible to split its vertices into two non-empty sets so that there is no edges between any two vertices from the same set.

Input file format

Input file contains integers N M, then M pairs of integers ai bi describing the edges of the graph.

Output file format

Output BIPARTITE if the graph is bipartite or NO if it is not.

Constraints

1 ≤ N ≤ 100000, 0 ≤ M ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2
1 2  1 3
BIPARTITE
2
4 6
1 2  2 3  3 4  4 1  1 3  2 4
NO

0.088s 0.019s 13