Description
Kirito's school has strict rules: he is required to arrive before 8:00 AM every day. However, Kirito has a bad habit of oversleeping. To avoid being late, Kirito bought a space-running device that allows him to travel at a speed of 2k kilometers per second, where k is any natural number.
Of course, the distance Kirito can travel is limited by the storage size of an int, meaning the total travel distance cannot exceed the maximum value of an int (in kilometers).
The route from Kirito's home to the school can be represented as a directed graph, with his home being node 1 and the school being node n. Each edge represents a distance of 1 kilometer.
Kirito wants to wake up as late as possible, so you need to help him determine the minimum number of seconds it will take him to reach the school. It is guaranteed that there is at least one path from node 1 to node n.
(Graph from Sample Input)
Input
The first line contains two integers, N and M, where N <= 800, M <= 10000, representing the number of nodes and edges.
The next M lines each contain two integers u and v, indicating a directed edge from node u to node v.
Output
Output a single number representing the minimum number of seconds it will take to reach the school.