D. [Sleeping Cup #11] D. The Lost Voucher

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

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

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

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

第一行两个正整数 。

下面 行，每行两个正整数 ，表示一条线路连接的两个站点。

保证输入的 对 两两不同。

一行一个整数表示答案。

特别地，如果不可能从 号站点坐公交车到 号站点，则输出 。

样例输入 #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

1

样例输入 #2

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

样例输出 #2

2

样例输入 #3

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

样例输出 #3

2

样例输入 #4

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

样例输出 #4

2

样例输入 #5

3 0

样例输出 #5

-1

样例 1 解释

不使用代金券，乘坐线路 ，花费 元。

样例 2 解释

预约线路 ，乘坐线路 ，花费 元。

样例 3 解释

预约线路 ，乘坐线路 ，花费 元。

样例 4 解释

不使用代金券，乘坐线路 ，花费 元。

样例 5 解释

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