Bicoloring#3165
In 1976, the Four Color Theorem was proven with the help of a computer. It states that any map can be colored using at most four colors so that no two adjacent regions share the same color.
In this problem, you are asked to solve a similar but simpler task. You need to determine whether a given connected graph is bipartite, that is, whether it is possible to color its vertices using only two colors so that no two adjacent vertices have the same color. For simplicity, the following conditions are assumed:
The graph contains no self-loops.
The graph is undirected: if vertex is connected to vertex , then vertex is also connected to vertex .
The graph is connected: there exists at least one path between any two vertices.
Consists of multiple test cases. Each test case begins with a line containing the number of vertices n~(0 \le n \le 1000). The second line contains the number of edges l~(1 \le l \le 250000). The following lines each contain two integers describing an edge between the corresponding vertices. The vertices of the graph are numbered with integers a~(1 \le a \le n). The last test case contains n = 0 and should not be processed.
For each test case, determine whether the graph can be colored using two colors, and print the corresponding message as shown in the sample.
Example 1