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

Ural Championship 2012

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Travel in Time

Time limit: 3.0 second
Memory limit: 64 MB
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.

Input

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.

Output

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.

Sample

inputoutput
4 3
1 2 10 20
2 4 50 20
4 3 20 30
1 3 10 30
3
1 2 3
Problem Author: Dmitry Ivankov
Problem Source: Ural Championship 2012
To submit the solution for this problem go to the Problem set: 1905. Travel in Time