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
注意
在第一个测试用例中,图表如下所示:
在第二个测试用例中,图表如下所示: