Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 13 Contest LoginRegister Exam
2017 ACM 集训队预选排名~      报名入口
Problem 1078. -- Bicoloring

Bicoloring

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 15  Solved: 9
[Submit][Status][Discuss]

Description

The four-color theorem states that every planar map can be colored using only four colors in such a way that no region is colored using the same color as a neighbor. After being open for over 100 years, the theorem was proven in 1976 with the assistance of a computer. Here you are asked to solve a simpler problem. Decide whether a given connected graph can be bicolored, i.e., can the vertices be painted red and black such that no two adjacent vertices have the same color. To simplify the problem, you can assume the graph will be connected, undirected, and not contain self-loops (i.e., edges from a vertex to itself).

Input

The input consists of several test cases. Each test case starts with a line containing the number of vertices n, where 1 < n < 200. Each vertex is labeled by a number from 0 to n - 1. The second line contains the number of edges l. After this, l lines follow, each containing two vertex numbers specifying an edge. An input with n = 0 marks the end of the input and is not to be processed.

Output

Decide whether the input graph can be bicolored, and print the result as shown below.

Sample Input

3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0

Sample Output

NOT BICOLORABLE.
BICOLORABLE

HINT

Source

[Submit][Status][Discuss]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin