← 返回题目列表

Codeforces · 1873/H

H. 疯狂之城

中文机器翻译题面 查看原题

Marcel 和 Valeriu 身处疯狂之城,该城市以 $$$n$$$ 建筑物为代表,其间有 $$$n$$$ 双向道路。

Marcel 和 Valeriu 分别从建筑物 $$$a$$$ 和 $$$b$$$ 开始。马塞尔想追上瓦莱留,换句话说,就是和他在同一栋楼里,或者在同一条路上见面。

在每次移动过程中,他们选择前往当前建筑物的相邻建筑物或留在同一建筑物中。因为瓦莱留非常了解马塞尔,所以瓦莱留可以预测马塞尔下一步会走向何方。瓦莱里乌可以利用这些信息来采取行动。他们同时开始和结束移动。

保证任意一对建筑物都通过某条路径连接,并且任意一对建筑物之间至多有一条道路。

假设两名玩家都发挥最佳状态,请回答 Valeriu 是否有无限期逃离马塞尔的策略。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含三个空格分隔的整数 $$$n$$$, $$$a$$$, $$$b$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq a, b \leq n$$$) - 建筑物的数量(等于道路的数量)以及 Marcel 和的起始建筑物瓦莱留。

以下 $$$n$$$ 行每行包含两个整数 $$$u_i$$$、$$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) - 建筑物 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条路。任何无序的一对建筑物之间至多有一条道路。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

给出的道路可以从任何建筑物到达沿道路的任何其他建筑物。

输出

对于每个测试用例,如果 Valeriu 可以永远逃脱 Marcel,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

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

输出 #1

YES
NO
YES
NO
NO
YES

注意

在第一个测试用例中,图表如下所示:

在第二个测试用例中,图表如下所示: