题目描述

小偷跑了！

我们可以把他所处的城市看作一个无向图，其中节点代表十字，边代表街道。交叉标记从 $0$ 到 $N–1$。

狡猾的小偷开始从十字街逃跑。每时每刻他都会走向一个相邻的十字路口。更确切地说，假设他在t的时候在 $u$ 十字路口。当且仅当十字路口 $u$ 和 十字路口 $v$ 之间有一条街道时，他可能在 $t+1$ 时刻出现在 $v$ 十字路口。请注意，他可能不会在两个连续的时刻停留在同一个十字路口。

警察想知道小偷是否有可能出现在这个城市的任何一个十字路口。

输入格式

输入包含多个测试用例：

在输入的第一行有一个整数 $T$，它是测试用例的数量。然后给出T测试用例的描述。

对于任何测试用例，第一行包含三个整数 $N$，$M$ 和 $S$ 。$N$ 是十字路口数，$M$ 是街道的数，$S$ 是小偷开始逃跑的十字路口。

对于接下来的 $M$ 行，每行中有 $2$ 个整数 $u$ 和 $v$（ $0 \le u,v \lt N$），表示在十字路口 $u$ 和 十字路口 $v$ 之间有一条没有方向的街道。

输出格式

对于每个测试用例，输出一行，以判断是否有一个时间小偷可能出现在任何十字路口处。查看输出格式的示例输出。

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

Case 1: YES
Case 2: NO

样例分析

如上所述。

数据范围与提示

对于 $100\%$ 的数据：$2 \le n \leq 10^5$，$1 \le m \leq 5\times 10^5$。