## Problem

In 1976 the “Four Color Map Theorem” was proven with the assistance of a computer. This theorem states that every map can be colored using only four colors, in such a way that no region is colored using the same color as a neighbor region.
Here you are asked to solve a simpler similar problem. You have to decide whether a given arbitrary connected graph can be bicolored. That is, if one can assign colors (from a palette of two) to the nodes in such a way that no two adjacent nodes have the same color. To simplify the problem you can assume:

• no node will have an edge to itself.
• the graph is nondirected. That is, if a node a is said to be connected to a node b, then you must assume that b is connected to a.
• the graph will be strongly connected. That is, there will be at least one path from any node to any other node.

### Input

The input consists of several test cases. Each test case starts with a line containing the number n (1 < n < 200) of different nodes. The second line contains the number of edges l. After this, l lines will follow, each containing two numbers that specify an edge between the two nodes that they represent. A node in the graph will be labeled using a number a (0 ≤ a < n). An input with n = 0 will mark the end of the input and is not to be processed.

### Output

You have to decide whether the input graph can be bicolored or not, and print it as shown below.

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

NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.

## 문제 풀이

이분 그래프 검사를 이용해서 간단하게 풀 수 있다.

## 답안 코드

``````#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

#define MAX_N   200

int n, l;

int q[MAX_N], wq, rq;
int color[MAX_N];

int main(){
while(true){
scanf("%d\n", &n);
if(n == 0)  break;

scanf("%d\n", &l);
int a,b;
for(int i = 0; i < l; ++i){
scanf("%d %d\n", &a,&b);
}

memset(color,-1,sizeof(color));

wq = rq = 0;
q[wq++] = 0;
color = 0;
bool isBipartite = true;
while(wq > rq){
int u = q[rq++];
for(int i = 0; i < adj[u].size(); ++i){
if(color[v] == -1){
q[wq++] = v;
color[v] = 1 - color[u];    // color 반전
}
else if(color[v] == color[u]){
isBipartite = false;
wq = rq = 0;
break;
}
}
}
if (isBipartite)
printf("BICOLORABLE.\n");
else
printf("NOT BICOLORABLE.\n");

for(int i = 0; i < n; ++i)