Distant Jumping

The country of Smoothland has N cities connected with M bidirectional roads. Recently one of Smooth- ish scientists invented a travelling device called jumper. The jumper can jump from city A to city B if there is a way from A to B over the roads containing at most three roads. The scientist wants to test his jumper the following way. He starts from the Smoothish capital and jumps until he returns to the capital, visiting each city exactly once (actually, he visits the capital twice). Your task is to find a sequence of the scientist’s jumps. Note: you visit only the cities you jump to, not the cities on the way which produces the jump. Input The first line of the input contains the number of the test cases, which is at most 15. The descriptions of the test cases follow. The first line of a test case description contains two integers N and M (2 ≤ N ≤ 2000, 0 ≤ M ≤ 50000) separated by a space. Each of the next M lines contains two numbers A and B (1 ≤ A, B ≤ N, A ̸= B) representing the road between city A and city B. For any two cities, there is at most one road between them. The cities are numbered from 1; the capital city is the city 1. The test cases are separated by blank lines. Output For each test case in the input, output ‘Impossible’ (without quotes) if there is no appropriate jump sequence. Otherwise output the sequence of jump descriptions separated by spaces and/or return symbols. The jump from city A to city B is outputted in the following way: the number of roads in the way corresponding to the jump (must be 1, 2, or 3), and the cities on this way starting at city A and ending at city B. If there are several solutions, output any of them. Print a blank line between test cases. Sample Input 2 66 12 23 13 14 45 56 20 Sample Output 112 123 2314 145 156

2/2 36541 Impossible