该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

注意

本题需要使用文件读写（voucher.in / voucher.out）。

题目描述

Sleeping Cup 王国有 $n$ 个公交站点和 $m$ 条双向的公交线路，每条线路票价 $1$ 元，连接两个不同的站点，且不存在连接了相同的两个站点的线路。

Sleeping Kangaroo 有一张公交公司的代金券，在代金券上写上始发站点和终到站点，它就可以预约一条新线路（新线路是单向的，既可以是已有的线路也可以是原先不存在的线路），且它可以免费乘坐该线路的公交车。

尽管这一服务允许先坐到终到站点再上交代金券，但粗心的 Sleeping Kangaroo 将这张代金券遗失在了 $1$ 号站点。也就是说，为了能够取到并使用代金券，新线路的始发站点和终到站点之一必须为 $1$ 号站点。

Sleeping Kangaroo 现在在 $2$ 号站点，它想坐公交车到 $3$ 号站点，那么它至少要付多少元钱？（可以选择使用或不使用代金券，代金券的成本不计）

输入格式

第一行两个正整数 $n, m\ (3 \le n \le 10^5, 0 \le m \le 2 \times 10^5)$。

下面 $m$ 行，每行两个正整数 $u_i, v_i\ (1 \le u_i < v_i \le n)$，表示一条线路连接的两个站点。

保证输入的 $\bm m$ 对 $\bm{(u_i, v_i)}$ 两两不同。

输出格式

一行一个整数表示答案。

特别地，如果不可能从 $\bm 2$ 号站点坐公交车到 $\bm 3$ 号站点，则输出 $\bm{-1}$。

样例

6 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6

1

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

2

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

2

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

2

3 0

-1

样例 1 解释

不使用代金券，乘坐线路 $2 \leftrightarrow 3$，花费 $1$ 元。

样例 2 解释

预约线路 $1 \to 3$，乘坐线路 $2 \leftrightarrow 6 \leftrightarrow 1 \to 3$，花费 $2$ 元。

样例 3 解释

预约线路 $2 \to 1$，乘坐线路 $2 \to 1 \leftrightarrow 5 \leftrightarrow 3$，花费 $2$ 元。

样例 4 解释

不使用代金券，乘坐线路 $2 \leftrightarrow 6 \leftrightarrow 3$，花费 $2$ 元。

样例 5 解释

可以证明，此时不可能从 $2$ 号站点坐公交车到 $3$ 号站点。