## Welcome To SDIBT ACM-ICPC Online Judge

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