H. Безумный город
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Марсель и Валериу находятся в безумном городе, который представляет собой $$$n$$$ зданий с $$$n$$$ двусторонними дорогами между ними.

Марсель и Валериу начинают в зданиях $$$a$$$ и $$$b$$$ соответственно. Марсель хочет поймать Валериу, то есть оказаться в том же здании, что и он, или встретиться на одной дороге.

Во время каждого хода они выбирают, пойти в соседнее здание от текущего или остаться в том же здании. Поскольку Валериу хорошо знает Марселя, Валериу может предсказать, куда Марсель пойдет в следующем ходу. Валериу может использовать эту информацию, чтобы сделать свой ход. Они начинают и заканчивают ход одновременно.

Гарантируется, что любая пара зданий соединена некоторым путем, и между любой парой зданий есть не более одной дороги.

Предполагая, что оба игрока играют оптимально, ответьте, есть ли у Валериу стратегия, чтобы бесконечно уходить от Марселя.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа, разделенных пробелом: $$$n$$$, $$$a$$$, $$$b$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq a, b \leq n$$$) — количество зданий (которое равно количеству дорог) и начальные здания Марселя и Валериу.

Следующие $$$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$$$.

Дороги заданы таким образом, что можно добраться из любого здания в любое другое, двигаясь по дорогам.

Выходные данные

Для каждого набора входных данных выведите «YES», если Валериу может бесконечно уходить от Марселя, и «NO» в противном случае.

Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

Пример
Входные данные
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
Выходные данные
YES
NO
YES
NO
NO
YES
Примечание

В первом примере граф выглядит следующим образом:

Марсель начинает в здании $$$2$$$, а Валериу начинает в здании $$$1$$$. Валериу знает, каким путем Марсель будет двигаться вокруг треугольника, и он может просто всегда двигаться так же, чтобы всегда избегать Марселя.

Во втором примере граф выглядит следующим образом:

Марсель начинает в здании $$$1$$$, а Валериу начинает в здании $$$4$$$. Марсель может пойти в здание $$$4$$$ на своем первом ходу и победить, так как Валериу должен либо пойти в здание $$$1$$$ (тогда они встретятся на дороге от $$$1$$$ до $$$4$$$), либо остаться в здании $$$4$$$ (тогда они встретятся в здании $$$4$$$). Таким образом, у Валериу нет стратегии для победы.