Description

Xiao A’s job is not only tedious but also has strict rules: he must arrive at the company before $6:00$ every morning, otherwise his salary for the month will be zero. However, Xiao A has a bad habit of sleeping in. To save his salary, he bought a space “running” device that can run $2^k$ kilometers per second (where $k$ is any natural number). Of course, this machine stores values using longint, so the total running length cannot exceed maxlongint kilometers. The route from Xiao A’s home to the company can be modeled as a directed graph: Xiao A’s home is node $1$, the company is node $n$, and each edge has length one kilometer. Xiao A wants to wake up as late as possible every day, so he asks you to compute the minimum number of seconds he needs to reach the company. It is guaranteed that there is at least one path from $1$ to $n$.

Input Format

The first line contains two integers $n, m$, representing the number of nodes and the number of edges.

The next $m$ lines each contain two integers $u, v$, indicating a directed edge from $u$ to $v$.

Output Format

Output a single number on one line, representing the minimum number of seconds needed to reach the company.

4 4
1 1
1 2
2 3
3 4

1

Hint

【Sample Explanation】

$1 \to 1 \to 2 \to 3 \to 4$, the total path length is $4$ kilometers, so using the running device once is enough.

【Constraints】

$50\%$ of the testdata satisfies that the optimal path length $\leq 1000$;

$100\%$ of the testdata satisfies $2 \leq n \leq 50$, $m \leq 10 ^ 4$, and the optimal path length $\leq$ maxlongint.

Translated by ChatGPT 5