You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

到了2026年，做核酸已经成了一件非常神奇的事。

Description

一共有n个石礅，编号从1~n。1号石礅是做核酸的地方，非常巨大，可以容纳114514个人。除1号石礅外，其他所有石礅都只能容纳一个人。有m条路，每条路连接两个石礅。在0时刻，除1号石礅外，每个石墩上都恰好有一个人。后面每一个时刻，每个人都有选择权：

1. 通过路移动到核酸地点或另一个空石礅。(如果相邻石墩有人, 必须等待这个人移动完毕, 才能走到该石墩上)
2. 呆在原地不动（无法移动）

• 土拨鼠博博现在在k号石礅，请你告诉他，他最快可以在几时刻到达1号石礅（核酸地点）呢？

Format

Input

第一行三个整数，n，m，k。后面m行，每行两个整数a ，b，表示a号石礅和b号石礅之间有路。

Output

一个正整数v，表示博博最快可以在v时刻到达1号石礅（核酸地点），无解输出-1

Samples

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

3

5 4 5
1 2
2 3
3 4
4 5

7

Limitation

• 2-1
• 4-2
• 2-1

画个图细品。。。

1s, 1024KiB for each test case.

$5≤n≤10^6，5<=m<=2*10^6, 1≤k,a,b≤n，k≠1$