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 other 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. Any driver will agree to change his plate for another 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 contains an integer K that is a number of the acting buses excluding the new bus (1 ≤ K ≤ 1000). 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 integers T, S1 and S2 that are the number of the route of the new bus and the numbers on the plate given by the storekeeper (1 ≤ T, S1, S2 ≤ 2000; TS1; TS2).


If it is impossible to get the needed number by a sequence of changes, output “IMPOSSIBLE”. Otherwise output the least necessary number of changes M > 0 in the first line and then M lines with sequentially numbers of buses (not routes!) with drivers of which the plates must be changed. The buses are numbered from 1 to K as they are described in the input. If there are several optimal 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