{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe discovery of superluminal neutrinos gave birth to a whole chain of \r\nscientific achievements. At first, scientists were able to \r\naccelerate individual protons and neutrons to the superluminal speed, then the whole atoms, \r\nand soon small objects. But the most surprising effect was that the objects \r\naccelerated to the superluminal velocity along a closed \r\npath simply went into the past. Moreover, the construction of such an \r\naccelerator is so simple that even an ordinary microwave oven with a \r\nlittle refinement could send an unripe banana a week ago to make it ripe.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAlthough experiments on sending objects back gave excellent results, they \r\ndid not always go smoothly. Sometimes an object that was sent back in time \r\nfaced his version of the past. After one of such collisions a black hole \r\nappeared and managed to swallow half of the research laboratory \r\nbefore collapsing. Despite such incidents, the researchers continued to \r\nwork on a stable displacement of large objects. Soon the transport ship \r\n“Valkyrie-500” entered mass production. With the help of \r\nsuperluminal drive it could arrive to the destination before the time of departure.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIntelligence reported that the rebel leader is coming to visit \r\none of the distant planets. You, the most talented special agent, are \r\ndelegated to destroy him at the moment of arrival before the press \r\ngets hold of him. You have a schedule of all flights of “Valkyries” in this \r\nsector of the Galaxy and the ability to use any of them. But remember that \r\nif you will be at least twice in the same planet at the same time, \r\nyou risk facing yourself. Since such a meeting would likely be fatal, \r\nit cannot be allowed until the job is done.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains integers \u003ci\u003en\u003c/i\u003e and \u003ci\u003em\u003c/i\u003e that are the total \r\nnumber of planets in the sector and flights of “Valkyries” between them \r\n\u003cnobr\u003e(1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e;\u003c/nobr\u003e \u003cnobr\u003e0 ≤ \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e)\u003c/nobr\u003e. \r\nIn the following \u003ci\u003em\u003c/i\u003e lines the flights are described. A description of \r\neach flight consists of the four integers: the numbers of planets of \r\ndeparture and arrival, time of departure and time of arrival. The last \r\nline consists of four integers: the number of the planet, where you \r\nare, the number of the planet which the rebel leader arrives to, the current time and the time when the rebel leader arrives. \r\nAll moments of time are integers from 0 to 10\u003csup\u003e6\u003c/sup\u003e. \r\nThe planets are numbered with integers from 1 to \u003ci\u003en\u003c/i\u003e. \u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIf the route does not exist, output “Impossible”. Otherwise, in the first\r\nline output number \u003ci\u003ek\u003c/i\u003e. In the second line output \u003ci\u003ek\u003c/i\u003e integers that are \r\nthe numbers of flights which are used in the order of the route. If there are several \r\nways to get to the destination, output any of them. Flights are \r\nnumbered with integers from 1 to \u003ci\u003em\u003c/i\u003e in the same order as they are described in the input. \u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3\r\n1 2 10 20\r\n2 4 50 20\r\n4 3 20 30\r\n1 3 10 30\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1 2 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}