Processing math: 100%

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

1N100000, 0M1000000

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.057s 0.008s 13