The discovery of superluminal neutrinos gave birth to a whole chain of
scientific achievements. At first, scientists were able to
accelerate individual protons and neutrons to the superluminal speed, then the whole atoms,
and soon small objects. But the most surprising effect was that the objects
accelerated to the superluminal velocity along a closed
path simply went into the past. Moreover, the construction of such an
accelerator is so simple that even an ordinary microwave oven with a
little refinement could send an unripe banana a week ago to make it ripe.
Although experiments on sending objects back gave excellent results, they
did not always go smoothly. Sometimes an object that was sent back in time
faced his version of the past. After one of such collisions a black hole
appeared and managed to swallow half of the research laboratory
before collapsing. Despite such incidents, the researchers continued to
work on a stable displacement of large objects. Soon the transport ship
“Valkyrie-500” entered mass production. With the help of
superluminal drive it could arrive to the destination before the time of departure.
Intelligence reported that the rebel leader is coming to visit
one of the distant planets. You, the most talented special agent, are
delegated to destroy him at the moment of arrival before the press
gets hold of him. You have a schedule of all flights of “Valkyries” in this
sector of the Galaxy and the ability to use any of them. But remember that
if you will be at least twice in the same planet at the same time,
you risk facing yourself. Since such a meeting would likely be fatal,
it cannot be allowed until the job is done.
The first line contains integers n and m that are the total
number of planets in the sector and flights of “Valkyries” between them
(1 ≤ n ≤ 105; 0 ≤ m ≤ 105).
In the following m lines the flights are described. A description of
each flight consists of the four integers: the numbers of planets of
departure and arrival, time of departure and time of arrival. The last
line consists of four integers: the number of the planet, where you
are, the number of the planet which the rebel leader arrives to, the current time and the time when the rebel leader arrives.
All moments of time are integers from 0 to 106.
The planets are numbered with integers from 1 to n.
If the route does not exist, output “Impossible”. Otherwise, in the first
line output number k. In the second line output k integers that are
the numbers of flights which are used in the order of the route. If there are several
ways to get to the destination, output any of them. Flights are
numbered with integers from 1 to m in the same order as they are described in the input.
1 2 10 20
2 4 50 20
4 3 20 30
1 3 10 30
1 2 3
Problem Author: Dmitry Ivankov
Problem Source: Ural Championship 2012