珅泽教育的刘老师正在准备一项寻路实践，他请小珅完成下面的任务。

有 $N$ 座城市，部分城市对之间修有铁路。任意两座不同城市之间，若没有铁路就有一条公路，若有铁路则没有公路。火车和汽车同时从城市 $1$ 出发前往城市 $N$，每走一条铁路或公路都花一分钟；同一种交通工具不能等待。

请安排两者路线，使它们都到达城市 $N$ 的时刻尽量早，并输出这个时刻；若其中一种交通工具无法到达，输出 $-1$。

输入格式

第一行输入 $N,M$。

接下来 M 行输入铁路连接的城市对。

输出格式

输出两者都到达所需的最少时间，无法完成输出 -1。

4 3
1 2
2 3
3 4

3

5 3
1 3
2 4
3 5

2

6 3
1 4
2 5
3 6

-1

数据范围与约定

• $2 \le N \le 400$
• $0 \le M \le N(N-1)/2$