练习专区

四色定理是一个著名的数学定理：如果在平面上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样。 现在把每一块区域当作一个顶点，是否有公共边当作是否相邻的关系，请你编程对所给的区域进行着色。区域按深搜（字母小的优先）的顺序进行，着色按red、yellow、blue、green的顺序进行，也就是说，一种颜色不能选择，就按顺序选下一种颜色。

输入有若干个案例，每个案例的第1行有两个数m、n，表示有m块区域、n种连接关系，接着有n行，每行两个整数i，j，表示i与j相连。

每个案例先输出一行“Case id:”，id从1开始，再输出各个顶点的颜色，格式见样例。