Jane lives in Byteland. There are only cities in Byteland. She has to start from the first city and travel precisely kilometers. There are exactly directed ways between the cities, two from each city. Distance from city to city is denoted by .
Can you help Jane find a way to do this?
If there are multiple solutions, the route should consist of the smallest number of nodes. Among all the routes with smallest number of nodes, print the lexicographically smallest solution.
Input Format
The first line of input contains . Each of the next lines contain two integers.
Line contains and .
Line contains and .
Line contains and .
Line contains and .
Line contains and .
All distances are in kilomeeters.
Constraint:
Output Format
On one line, print the route Jane has to travel (city numbers). If it's impossible, print .
Sample Input
5
3 1
1 2
1 3
2 2
1 1
Sample Output
1 2 4
Explanation
She has to travel from to and then from to .
This will be the shortest way to travel exactly kilometers. .