练习专区

今天的一小步就是明天的一大步

Problem 1602 深搜地图....数构

Accepted: 1 Total Submit: 6
Time Limit: 1000ms Memory Limit: 30720KB

Description

四色定理是一个著名的数学定理：如果在平面上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样。现在把每一块区域当作一个顶点，是否有公共边当作是否相邻的关系。请你编程把这个图中的区域按深搜的方式输出。

Input

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

Output

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

Sample Input

11 20
A B
A C
A D
B E
B C
C E
C F
C D
D F
D G
E H
E F
F H
G H
G I
H J
H I
J I
J K
I K

Sample Output

Case 1:ABCDFEHGIJK

Hint

提交　　　　　返回