练习专区

求图中两个顶点之间的简单路径。

输入有多种情况，每种情况的第一行有两个整数m、n（0<=m、n<100），m表示图中的顶点数，n表示弧的个数。接着有n行每行两个正整数v1、v2表示从顶点v1到v2有一条弧连接。顶点的序号从1开始。再后输入一个整数k，表示有K个情况要问，接着有k行输入，每行是要访问的起始顶点和结束顶点vb、ve。

输出按深搜的方法所经过的各顶点。格式见样例。

6 11
1 2
1 5
1 6
6 2 
6 5
6 4
2 4 
2 3
4 5
4 3
3 6
3
1 6
2 5
3 6

5 4
1 2
1 3
3 4
3 5
2
2 5
1 4

Case 1:
123456
215
321546
Case 2:
2135
134