**The 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 bi-colored. 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 non-directed. 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* ( ). 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 bi-colored or not, and print it 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.

using System;

using System.Collections.Generic;

using System.Text;

using System.IO;

using System.Collections;

using System.Text.RegularExpressions;

namespace ConsoleApplication1

{

class Edge

{

public int a = 0;

public int b = 0;

}

class Program

{

static void Main(string[] args)

{

Console.Write("Enter number of nodes: ");

int numberOfNodes = int.Parse(Console.ReadLine().ToString());

int[] node = new int[numberOfNodes];

//Initializing the node array to -1

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

{

node[i] = -1;

}

Console.Write("Enter number of edges: ");

int numberOfEdges = int.Parse(Console.ReadLine().ToString());

Edge[] edg = new Edge[numberOfEdges];

Console.WriteLine("Enter pairs of node connected separated by a space:");

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

{

edg[i] = new Edge();

Console.Write("");

string inputStr = Console.ReadLine();

Regex reg = new Regex(" ");

int flag = 0;

foreach (string val in reg.Split(inputStr))

{

if (flag == 0)

{

edg[i].a = int.Parse(val);

flag = 1;

}

else

{

edg[i].b = int.Parse(val);

}

}

}

bool check = true;

//Processing the edges for bi-coloring

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

{

if (node[edg[i].a] == -1 && node[edg[i].b] == -1)

{

node[edg[i].a] = 0;

node[edg[i].b] = 1;

}

else if (node[edg[i].a] == -1 && node[edg[i].b] > -1)

{

if (node[edg[i].b] == 0)

{

node[edg[i].a] = 1;

}

else

{

node[edg[i].a] = 0;

}

}

else if (node[edg[i].a] > -1 && node[edg[i].b] == -1)

{

if (node[edg[i].a] == 0)

{

node[edg[i].b] = 1;

}

else

{

node[edg[i].b] = 0;

}

}

else if (node[edg[i].a] > -1 && node[edg[i].b] > -1)

{

if (node[edg[i].a] == 0 && node[edg[i].b] == 1)

{

continue;

}

else if (node[edg[i].a] == 1 && node[edg[i].b] == 0)

{

continue;

}

else

{

Console.WriteLine("NOT BICOLORABLE.");

check = false;

break;

}

}

}

if (check)

{

Console.WriteLine("BICOLORABLE.");

}

}

}

}