Description

小黑子要完了,因为他不小心踩到了蓝色妖姬的切尔西，要求小黑子每天晚上在6:00之前回到家，否则蓝色妖姬将会发现他。可是他却有时候因为跑不过蓝色妖姬而被蓝色妖姬发现。于是为了安全，小黑子买了一个穿梭器，每秒钟可以跑 2^k千米（k是任意自然数）。当然，这个机器是用 longint 存的，所以总穿梭长度不能超过maxlongint 千米。小黑子的地点到家的路可以看做一个有向图，小黑子现在在的点（良心的出题人提示：这不是时间，是位置）为1，家的点为n，每条边长度均为一千米。小黑子想每天能回家尽量晚，所以让你帮他算算，他最少需要几秒才能到家。数据保证1到n至少有一条路径。

Input

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

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

Output

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

Samples

4 4
1 1
1 2
2 3
3 4

1

Limitation

1s, 1024KiB