Problem B. 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.042s 0.011s 15