背景

暑假又到啦！大家准备暑假去哪里玩呢？小方小块小鸟和家人们早就定好了暑假的出游计划，集中在七月中到八月初这段时间里出行。这天，他们来方块鸟分享了各自的出游计划。

描述

小鸟计划去爬安徽九华山。

小鸟其实已经来过安徽啦，不过他上次去的是黄山。九华山位于中国安徽省池州市青阳县境内，是中国四大佛教名山之一，是地藏菩萨的道场。九华山山势雄伟，自然风光和人文景观融为一体，有「东南第一山」之称。说起来，九华山，这个名字还是李白取的呢。据记载，唐朝天宝年间诗仙李白数游九华山后，看到此山秀异，九峰如莲花，触景生情，在与友人唱和了《改九子山为九华山联句并序》，其中有：「妙有分二气，灵山开九华」，从此，人们就将「九子山」改为「九华山」。

有了上次爬黄山的经验，小鸟对这次爬九华山有了更多的期待，既然来都来了，多看一点终归是好的嘛。他希望找到一条路线，从九华山大门（记为1号景点）出发，到达天台正顶（记为N号景点），沿途经可能多的游览景点，但又不走回头路（同一景点只能经过一次）。

请你编写程序，帮找出这条最长的路线。

数据输入保证只存在唯一的一条最长路线。

输入输出格式

输入

第一行包含一个正整数 $N$ ，表示景点的数量。 ( $1 < N ≤ 100$ )

第二行包含一个正整数 $M$，表示景点之间路径的数量。 ($1 ≤ M ≤ 1,000$)

随后 $M$ 行，每行包含两个以空格分割的正整数 $u$ 和 $v$，表示从 $u$号景点 到 $v$号景点 之间有路相连。 ( $1 ≤ u, v ≤ N$)

输出

一行，输出小鸟从山脚到山顶所能经过的最多景点数量。如果无法到达山顶，输出-1。

样例

6
7
1 2
1 3
2 4
2 5
3 5
5 6
1 6

4

样例一说明

从景点1出发，经过景点2、5，到达景点6，共经过4个景点。

3
2
1 2
2 3

3

样例二说明

从1号景点出发，经过2号景点，到达3号景点，共经过3个景点。