ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1096. Get the Right Route Plate!

Time limit: 1.0 second
Memory limit: 64 MB
Everybody who had ridden a Ekaterinburg bus could notice that on the inner side of the plate with the number of the route there was a number of another route.
One day the driver of a new bus came to the storehouse and found that there was no plate with the number of the route he had been assigned to ride. The storekeeper simply gave him a random plate and advised to change it for a plate from another bus. But the drivers who had the necessary plates did not need the plate given by the storekeeper. Any driver will agree to change his plate for another only if this plate has the number of his route. Help the new driver to find a shortest sequence of changes that will enable him to get a plate with the number of his route.


The first line contain the number K ≤ 1000 of the acting buses (excluding the new bus). The buses are numbered from 1 to K. The next K lines contain the number of the route of the corresponding bus and the number on the other side of its plate. Numbers of routes are integers from 1 to 2000.
The last line of the input contains the number of the route of the new bus and the numbers on the plate given by the storekeeper.


The first line of the output should contain the word IMPOSSIBLE if it is impossible to get the needed number by a sequence of changes otherwise it should contain the least necessary number of changes M > 0 followed by an M lines that contain sequentially numbers of buses (not routes!) with drivers of which the plates must be changed. If there are several solutions, you can output any one.


8 5
5 4
7 4
1 5
4 1 8
Problem Author: Stanislav Vasilyev
Problem Source: USU Open Collegiate Programming Contest March'2001 Senior Session