Whittington is showing his trained cat in its surprising feat of going from A to Z, grabbing all the mice in his way while stepping on each circle just once. You receive an arbitrary, undirected graph, where each node is identifed by a single upper- case letter. One vertex is the source, or starting point, and the other is the target, or end point. Your job is to imitate the cat’s ability, and identify a path that goes from the source to the target, visiting each node in the graph ex- actly once. If there is more than one valid path, choose the lexicographically lowest one. Input Whittington’s cat is very well trained Input starts with a positive integer T, that denotes the number of test cases. There’s a blank line at the beginning of each case. Then two integers are given in a single line: N and M, representing the number of nodes and the number of bi-directional edges in the graph, respectively. You can assume that there is at most one edge between any pair of nodes, and that each edge will be reported only once. The next line will contain N distinct letters, separated by spaces, which are the identifers for all the nodes in the graph. The frst letter in this list will be the source, the last letter will be the target. All letters will be uppercase letters from the English alphabet. Then M lines will be presented, describing the edges of the graph. Each of these lines contain two distinct letters, which describe two nodes that are connected by an edge. T ≤ 60; 2 ≤ N ≤ 15 Output For each test case, print the case number, followed by the sequence of letters that describe the path from the source to the target, visiting all nodes exactly once. If a valid solution doesn’t exist, print the word ‘impossible’. Sample Input 3 12 14 ABCDEFUVWXYZ AF AV BU BW CD
2/2 CV DY DW EX EZ FU FY UZ WX 32 ABC AB AC 45 LNIK LN IL IN KN KI Sample Output Case 1: AVCDYFUBWXEZ Case 2: impossible Case 3: LINK