No testdata at current.

题目描述

小Y要在城市里进行一场不间断的奔跑。我们可以把城市看作一张无向图，图中的点代表路口，边代表连接路口的道路。

小Y从S点（路口）出发，每个时刻他都只能跑到相邻的一个路口。假设在第t时刻小Y在U点，那么他一定会在第t+1时刻出现在与U点有道路相连的某个V点。注意：小Y不能停下来，他必须持续奔跑。

现在给定你N个点、M条边和起点S，请判断：是否存在某个时刻，使得小Y有可能出现在图中的任意一个结点？如果存在，输出YES；否则，输出NO。

输入格式

输入包含多个测试用例：

1. 第一行包含一个整数 T（T ≤ 10），表示测试用例的数量。
2. 对于每个测试用例：
   • 第一行包含三个整数 N（≤ 100,000）、M（≤ 500,000）和 S。
     • N 是十字路口的数量，M 是街道的数量，S 是小Y开始奔跑的十字路口的索引。
   • 接下来 M 行，每行包含两个整数 u 和 v（0 ≤ u, v < N），表示十字路口 u 和 v 之间有一条无向街道。

输出格式

对于每组测试数据，如果存在一个时刻，小Y可能出现在任何位置，输出 YES，否则输出 NO。

2
3 3 0
0 1
0 2
1 2
2 1 0
0 1

Case 1: YES
Case 2: NO