Description

XRJ 得到了一张无向图，这张图上有$n$个点$m$条边，保证图的点集可以分成两个部分，使得每个部分的点之间均没有任何边相连。点的编号从$1$到$n$， XRJ 希望找到一个最大的正整数$k$，使得存在一种用$2^k$种颜色将每条边染色的方案满足与任何一个点相邻的边中包含了所有颜色且每种颜色的边的数量相等，并告诉他一组方案。

注意，这意味着如果一个点不与任何边相邻，那么将不存在方案。

Input Format

输入文件名为coloration.in。

每个测试点中包含多组数据，对于每组数据：

输入文件第一行两个正整数$m,n$，用一个空格隔开，表示图的边数和点数。

接下来$m$行，每行两个正整数$x,y$，表示一条从点$x$到点$y$的无向边，保证$x$和$y$均为合法编号且$x≠y$。

数据以一行0 0结束（不包含引号）。

Output Format

输出文件名为coloration.out。

对于每组数据：

如果不存在这样的正整数k则输出一行-1，否则第一行输出一个数，表示最大的$k$，第二行输出$m$个用空格隔开的数，第$i$个数表示第$i$条边的颜色颜色用$1$到$2k$的数字表示。若有多种方案，输出任意一种方案即可。

Sample

样例输入 1

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

样例输出 1

1
1 2 2 1 1 2 1 2

样例解释 1

以上给出了最大的$k$和一种合法的输出，若你的输出和上面的输出不符，可以手工检查方案的正确性。

Hint

对于$10\%$的数据：$m\le 7$。
对于$30\%$的数据：$m\le 100$。
对于$50\%$的数据：$m\le 1\ 000$。
另有$20\%$的数据：$k=1$。
对于$100\%$的数据：$m,n\le 100\ 000$，保证图的点集可以分成两个部分，使得每个部分的点之间均没有任何边相连。