四色定理可做如下的表述：
对平面上的地图染色，最多使用4种颜色就可性使任何两个相邻区域具有不同的颜色。
虽然称为"定理，但上述结论至今并没有得到纯理论的证明。1976年，K.I.阿佩尔与W.哈肯利用计算机将全部平面图归类为1936个可约构形，对每个构形都用计算机验证了上述断言成立，从而宣布四色定理得到证明。这一成果在当时轰动了全世界。虽然至今仍有许多人对这种证明方法执有异议，但没有人否定这个定理的正确性。
所谓平面图，是指画在平面上的无向图，任何两边都不相交（例如5个结点的完全图，就不是平面图）。通常的地图，如果把区域退缩为一点，两区域相邻，就用一条边连接两点，就构成了一个平面图。具有n的结点的平面图可用一个n*n的邻接矩阵来表示：如果a[i][j]=1，表示结点i与结点j相邻；如果a[i][j]=0，表示结点i与结点j不相邻。
输入一个平面图的邻接矩阵，用1,2,3,4分别表示4种颜色，输出字典序最小的满足要求的染色方案。
第一行两个数N,M，表示平面图的节点数与边数。
接下来第2到M+1行，每行两个用空格隔开的数X,Y，表示X点与Y点间有边相连。
6 8
1 2
2 3
3 6
6 1
1 4
4 6
4 5
5 6
1
2
1
2
1
3