逃离星系1

时间限制：1000MS ｜ 空间限制：128MB ｜ 难度：Mid-

题目描述

小美驾驶飞船在1号星球执行任务，飞船添加完燃料后探测器发出警报，通知小美该星系将在10分钟后爆炸，到时飞船根本坚持不住，因此需要以最短的时间逃离。

从一个星球飞到另一个星球需要1分钟。由于燃料有限，每到达一个星球，都需要消耗1分钟添加燃料，再继续飞行。

请你根据星系地图，计算飞船能否在爆炸前到达出口星球h。

注意：如果飞船到达h添加完燃料刚好10分钟，也算逃离成功。

输入格式

第一行两个整数表示星球数量n和航行道路的数量m。（n<=50）

接下来m行，每行两个整数x和y，表示x和y星球间存在一条航行道路。

最后一行一个整数h，表示出口的编号。

注意：星球编号从1至n，出口h在范围之内但不是1号星球；航道是双向通道。

输出格式

飞船逃离成功输出"YES"；否则输出"NO"。

样例1

输入

8 10
2 7
2 4
1 4
1 5
4 5
5 6
2 6
6 3
3 2
8 3
8

输出

YES

样例2

输入

10 11
2 1
1 6
2 6
3 7
7 6
4 3
9 5
3 5
8 9
3 10
4 10
8

输出

NO

数据范围

n<=50，星球编号从1至n，出口h在范围之内但不是1号星球，航道是双向通道。

知识点与难度

• 难度：Mid-
• 知识点：搜索基础（BFS/DFS）
• 原标签：搜索基础、第二十三讲(Level3)
• GESP定级：6级

测试点分布