M wolves and N dogs, where M <= N, need to cross a river from its west bank to the east bank using a boat which can hold at most two individuals. Safety constraint: the number of dogs, unless it is zero, is never less than of wolves on either bank or on the boat. General constraint: the boat needs to carry at least one individual on its way to the east bank or back to the west bank. Is it possible to cross the river without the dogs being eaten? If yes, how can we move them? Give one legal moving sequence.
This problem can be modeled by using simply the information of the occupants on the west bank, and the position of the boat. Let us use (X, Y, P)-triples to denote different states in the process of moving, where X Y and P are the numbers of wolves and dogs on the west bank and the position (west W or east E) of the boat at beginning of after a legal move, respectively. For example, the initial state is (M, N, W) and the final state is (0, 0, E). A safety state (m, n, P) for this problem will be n >= m, unless n = 0, and (N - n) >= (M - m), unless N - n = 0 (i.e., the number of dogs on either the west bank or the east bank is never less than that of the wolves at any time).
Write a program given pairs of the beginning numbers of wolves and dogs (stored in the file river.dat) will output results, separately. Each result is either a legal moving sequence, an ordered transition from the initial safe state (M, N, W) to the final state (0, 0, E), if there exists a solution, or the message \'Impossible.\' if no any solution exists. Meanwhile, a circular (or useless) moving process, i.e., from a state to a state itself after zero or several moves (transitions), is not allowed to be included in a legal moving sequence.
For example, let M = 2 and N = 2. One legal moving sequence is
(2, 2, W) -> (0, 2, E) -> (1, 2, W) -> (1, 0, E) -> (2, 0, W) -> (0, 0, E).
where w1 d1, w2 d2, and w3 d3 are the beginning numbers (integers) of wolves and dogs in the different lines. There is one space between each of the w1 d1, w2 d2 and w2 d3 pairs.
(2, 2, W)
(0, 2, E)
(1, 2, W)
(1, 0, E)
(2, 0, W)
(0, 0, E)
One blank line is required for separating each of the output results. If there is no sequence of legal moves then output signle line containg