Problems
Longest Flight Route
Longest Flight Route
Uolevi has won a contest, and the prize is a free flight trip that can consist of one or more flights through cities. Of course, Uolevi wants to choose a trip that has as many cities as possible.
Uolevi wants to fly from Syrjälä to Lehmälä so that he visits the maximum number of cities. You are given the list of possible flights, and you know that there are no directed cycles in the flight network.
\InputFile
The first line has two integers $n\:(2 \le n \le 10^5)$ and $m\:(1 \le m \le 2 \cdot 10^5)$: the number of cities and flights. The cities are numbered $1, 2, ..., n$. City $1$ is Syrjälä, and city $n$ is Lehmälä.
After this, there are $m$ lines describing the flights. Each line has two integers $a$ and $b\:(1 \le a, b \le n)$: there is a flight from city $a$ to city $b$. Each flight is a one-way flight.
\OutputFile
First print the maximum number of cities on the route. After this, print the cities in the order they will be visited. You can print any valid solution.
If there are no solutions, print \textbf{"IMPOSSIBLE"}.
\includegraphics{https://static.eolymp.com/content/ab/ab5dqm7um536r5nrddgbq5tvgk.gif}
Input example #1
5 5 1 2 2 5 1 3 3 4 4 5
Output example #1
4 1 3 4 5