Time Limit: 1000ms

Memory Limit: 65535KB

Description

徐老师下课看着同学们做老鹰抓小鸡的游戏,发现一个有趣的现象:对于一定的队形,下一个变换到的队形也是固定的几个(比如杨洁同学就喜欢紧跟翟尚进同学后面\(^o^)/~)。例如,队伍中5个人,从鸡妈妈往后面编号分别为01234,徐老师观察到下一个队形不是12430就是04123(或许1号是翟尚进,2号是杨洁小朋友O(∩_∩)O~)。

Input

对于每组数据,一个整数N(N<10)表示队伍中的总人数。然后是一个整数M(M<500000),表示M种可能的队形变换。接下来M行,每行为两个编号序列a和b,表示从a可以变换到b(a和b分别为从0~N-1的一个排列)。

Output

从输入中出现的编号最小的一个序列变换到输入中出现的编号最大的一个序列,最少要经过多少步变换,数据保证有解。(序列大小的定义你们懂的,理解为字典序或者数字大小均可)。

Sample Input

3  4
012  021
012  120
021  120
120  210

Sample Output

2

Hint

None

Source

陶树才

提交代码