Enchanted Object Search#1824
You are a seeker searching for a hidden object in an enchanted forest. The object is hidden behind the branches of one of the trees, out of your sight. You can inspect ("search") any of the trees; if the object is in that tree, you find it instantly. If not, the object shifts, moving along the connections to a neighboring tree while you are busy searching, without your knowledge. It never stays in the same place after a search. You want to determine whether there is a search strategy that guarantees you will find the object regardless of its initial position and subsequent moves. If so, you must determine the shortest sequence of searches that guarantees success.
Figure 2
For example, consider the case where there are only two connected trees in the forest (left-hand side of Figure 2). It is then possible to guarantee a discovery by searching the same tree twice. If the object is there on your first search, you will find it. Otherwise, it must have been in the other tree and will switch when you search for the second time, ensuring you find it then.
However, depending on the structure of the forest, it may not be possible for you to ensure success. One such case is if there are three trees, all connected to each other (right-hand side of Figure 2). No matter where you search, there will always be two possible locations for the object at any given time. (Note that you must plan for the worst-case scenario where the object always anticipates your next search location.)
The input consists of several test cases, each separated by a single blank line. Each test case begins with a line containing two integers and (1 \leq n \leq 21); is the number of trees in the forest, and is the number of adjacency relations between trees. Each of the following lines contains two distinct integers between and n-1 (inclusive), the identifiers of the trees in an adjacent pair. The order of both trees within a pair carries no meaning, and no pair appears more than once. Furthermore, you may assume that no tree is adjacent to itself, and there is always a path between any two trees in the forest.
The test cases end with a line containing only two zeros (also preceded with a blank line).
Print a line for each test case. The line should contain the single word Impossible if the task is impossible. Otherwise, it must contain the shortest sequence of searches with the required property, in the format : V_1 V_2 ... V_L, where is the length of the sequence, and V_1, V_2, \ldots, V_L are space-separated integers containing the identifiers of the trees to search in the correct order. If several shortest sequences exist, print the lexicographically smallest one. (A sequence is lexicographically smaller than another if the first element in which they differ is smaller in the first one.)
Example 1