A graph, G, consists of a finite set of vertices, V, and a set of edges, E, where each edge is a set of 2 vertices {u, v}. A walk in G is a finite sequence of vertices (v1, v2, ... , vk), such that for each pair(vi−1,vi)foriin[2,k],{vi−1,vi}isinE.Thisiscalleda“walkfromv1 tovk”. IfVisasetof integers, then any two walks in G can be compared lexicographically; for example, the walk (3, 5, 6, 2, 8) is smaller than the walk (3, 5, 6, 5, 7). A walk, W, from a to b is lexicographically smallest if there is no other walk from a to b in G that is smaller than W. A drive is a walk (v1, v2, ..., vk), where no edge is used twice consecutively. That is, for all i from 2 up to k − 1, vi−1 is not equal to vi+1. Given G and a start vertex, s, your task is to find the lexicographically smallest drives from s to each vertex in G. Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing the integers n, m and s. (0 ≤ n ≤ 100, 0 ≤ m ≤ 4950). The next m lines will list the edges of G. V is the set {0,1,...,n−1}. s is in V. Output For each test case, output the line ‘Case #x:’, where x is the number of the test case. Then print n lines, line i listing the lexicographically smallest drive from s to i using single spaces to separate consecutive vertices. If there is no such drive, print ‘No drive.’ Put an empty line after each test case. Sample Input 2 645 50 25 40 31 440 01 12 02 03 Sample Output Case #1: 50 No drive. 52 No drive. 504 “OK. Let’s go right.” Bartholomew Furrow
2/2 5 Case #2: 0 01 012 No drive.