The country of Smoothland has N cities connected with M bidirectional roads. Recently one of Smoothish 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.
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.
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.
| Input | Output |
2 6 6 1 2 2 3 1 3 1 4 4 5 5 6 2 0 | 1 1 2 1 2 3 2 3 1 4 1 4 5 1 5 6 3 6 5 4 1 Impossible |