1976年，在计算机的帮助下证明了“四色图定理”。该定理指出，每个地图只能使用四种颜色着色，这样就不会有任何区域使用与相邻区域相同的颜色着色。

在这里，你被要求解决一个更简单的类似问题。你必须决定给定的任意连通图是否可以是双色的。也就是说，如果可以将颜色（从两个调色板中）分配给节点，使得没有两个相邻节点具有相同的颜色。为了简化问题，您可以假设：

任何节点都不会有自己的边。

该图是无向的。也就是说，如果说节点a连接到节点b，那么你必须假设b连接到a。

该图将是强连接的。也就是说，从任何节点到任何其他节点都至少有一条路径。

输入

输入由几个测试用例组成。每个测试用例都以一行开始，该行包含不同节点的编号n（1<n<200）。第二行包含边的数量l。之后，将有l行，每行包含两个数字，指定它们所表示的两个节点之间的边。图中的节点将使用数字A（0≤A<n）标记。

n=0的输入将标记输入的结束，不进行处理。

输出

您必须决定输入图是否可以双色，并按如下所示打印。