#215. 做核酸(2)
做核酸(2)
Background
到了2026年,做核酸已经成了一件非常神奇的事。
Description
一共有n个石礅,编号从1~n。1号石礅是做核酸的地方,非常巨大,可以容纳114514个人。除1号石礅外,其他所有石礅都只能容纳一个人。有m条路,每条路连接两个石礅。在0时刻,除1号石礅外,每个石墩上都恰好有一个人。后面每一个时刻,每个人都有选择权:
- 通过路移动到核酸地点或另一个空石礅。(如果相邻石墩有人, 必须等待这个人移动完毕, 才能走到该石墩上)
- 呆在原地不动(无法移动)
- 土拨鼠博博现在在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.
Statistics
Related
In following contests: