D. Величественная коричневая древесная змея
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Существует неориентированное дерево, состоящее из $$$n$$$ вершин, соединенных $$$n-1$$$ двусторонним ребром. Также есть змея, находящаяся внутри этого дерева. Ее голова находится в вершине $$$a$$$ и ее хвост находится в вершине $$$b$$$. Тело змеи занимает все вершины на простом пути между вершинами $$$a$$$ и $$$b$$$.

Змея хочет узнать, может ли она развернуться, то есть переместить свою голову в вершину, где начинался хвост и переместить свой хвост в вершину, где начиналась голова. К сожалению, движения змеи ограничены структурой дерева.

За одну операцию змея может переместить свою голову в соседнюю вершину, которая не занята змеей в текущий момент. Когда это происходит, хвост змеи перемещается на одну вершину ближе к голове, то есть длина змеи не изменяется. Аналогично, змея может переместить свой хвост в соседнюю вершину, которая не занята змеей в текущий момент. Когда это происходит, голова змеи перемещается на одну вершину ближе к хвосту.

Будем обозначать позицию змеи, как $$$(h,t)$$$, где $$$h$$$  — это номер вершины дерева, в которой находится голова и $$$t$$$  — номер вершины дерева, где находится хвост. Змея сможет развернуться с помощью последовательности операций $$$(4,7)\to (5,1)\to (4,2)\to (1, 3)\to (7,2)\to (8,1)\to (7,4)$$$.

Определите, сможет ли змея развернуться с помощью некоторой последовательности операций.

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

В первой строке находится единственное целое число $$$t$$$ ($$$1\le t\le 100$$$)  — количество наборов входных данных. Следующие строки содержат описания наборов входных данных.

В первой строке каждого набора входных данных находится три целых числа $$$n,a,b$$$ ($$$2\le n\le 10^5,1\le a,b\le n,a\ne b$$$).

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u_i,v_i$$$ ($$$1\le u_i,v_i\le n,u_i\ne v_i$$$), обозначающих ребро между вершинами $$$u_i$$$ и $$$v_i$$$. Гарантируется, что данные ребра образуют дерево.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

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

Пример
Входные данные
4
8 4 7
1 2
2 3
1 4
4 5
4 6
1 7
7 8
4 3 2
4 3
1 2
2 3
9 3 5
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
16 15 12
1 2
2 3
1 4
4 5
5 6
6 7
4 8
8 9
8 10
10 11
11 12
11 13
13 14
10 15
15 16
Выходные данные
YES
NO
NO
YES
Примечание

Первый набор входных данных изображен на картинке в тексте условия задачи.

Во втором наборе входных данных дерево имеет форму пути. Можно показать, что змея не сможет развернуться.

В третьем наборе входных данных, можно показать, что змея не сможет развернуться.

В четвертом наборе входных данных пример последовательности операций:

$$$(15,12)\to (16,11)\to (15,13)\to (10,14)\to (8,13)\to (4,11)\to (1,10)$$$

$$$\to (2,8)\to (3,4)\to (2,5)\to (1,6)\to (4,7)\to (8,6)\to (10,5)$$$

$$$\to (11,4)\to (13,8)\to (14,10)\to (13,15)\to (11,16)\to (12,15)$$$.