当前没有测试数据。

1.跑路上班

题目描述

小明的工作不仅繁琐，更有苛刻的规定，要求小明每天早上在$6:00$之前到达公司，否则这个月工资清零。可是小明偏偏又有赖床的坏毛病。于是为了保住自己的工资，小明买了一个空间跑路器，每秒钟可以跑$2^{k}$千米（$k$是任意数）。当然，这个机器是用$longint$存的，所以总跑路长度不能超过$maxlongint$千米。小明的家到公司的路可以看做一个有向图，小明家为点$1$，公司为点$n$，每条边长度均为一千米。小明想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证$1$到$n$至少有一条路径。

输入格式

第一行两个整数$n$，$m$，表示点的个数和边的个数。

接下来$m$行每行两个数字$u$，$v$，表示一条$u$到$v$的边。

输出格式

一行一个数字，表示到公司的最少秒数。

数据范围与提示

记最优解路径长度为$answer$。

• 对于$50\%$的数据，$answer \leq 10^{3}$；
• 对于$100\%$的数据，$1 \leq n \leq 50$，$1 \leq m \leq 10^{4}$，$answer \leq max\ long\ int$。

样例

4 4
1 1
1 2
2 3
3 4

1

说明

$1 \to 1 \to 2 \to 3 \to 4$，总路径长度为$4$千米，直接使用一次跑路器即可。