题目描述

给定一个 n 个顶点 m 条边的无向图，顶点编号从 1 至 n。统计从顶点 1 出发到达终点 e 的最少步数（1<e ≤n）。

输入格式

第一行输入两个正整数 n 和 m，表示图的顶点数和边数。1≤n≤1000，1≤m≤10^5。 第二行开始，往后 m 行，每行输入两个以空格隔开的正整数 u,v，表示 u,v 顶点之间有一条边直接相连（u、v是顶点编号，数值范围是1~n）。数据保证没有重边。 最后一行一个正整数 e，表示终点编号。 数据保证图从起点1能到达顶点e。

输出格式

输出一个整数表示从顶点 1 出发到达终点 e 的最少步数。

样例

输入样例 1

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

输出样例 1

2

输入样例 2

9 12
1 3
1 2
2 4
2 7
3 4
3 5
4 6
4 8
5 6
6 9
7 8
8 9
9

输出样例 2

4

输入样例 3

9 12
1 3
1 2
2 4
2 7
3 4
3 5
4 6
4 8
5 6
6 9
7 8
8 9
2

输出样例 3

1