ROI-2006 - Bipartite graph

Problem C. Bipartite graph ≡

problems
visible spaces
basic formulae
wide text
editor

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 a_i b_i 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`