CF1381D.The Majestic Brown Tree Snake

There is an undirected tree of $n$ vertices, connected by $n-1$ bidirectional edges. There is also a snake stuck inside of this tree. Its head is at vertex $a$ and its tail is at vertex $b$. The snake's body occupies all vertices on the unique simple path between $a$ and $b$.

The snake wants to know if it can reverse itself — that is, to move its head to where its tail started, and its tail to where its head started. Unfortunately, the snake's movements are restricted to the tree's structure.

In an operation, the snake can move its head to an adjacent vertex not currently occupied by the snake. When it does this, the tail moves one vertex closer to the head, so that the length of the snake remains unchanged. Similarly, the snake can also move its tail to an adjacent vertex not currently occupied by the snake. When it does this, the head moves one unit closer to the tail.

Let's denote a snake position by $(h,t)$, where $h$ is the index of the vertex with the snake's head, $t$ is the index of the vertex with the snake's tail. This snake can reverse itself with the movements $(4,7)\to (5,1)\to (4,2)\to (1, 3)\to (7,2)\to (8,1)\to (7,4)$.

Determine if it is possible to reverse the snake with some sequence of operations.

有一棵包含 $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)$。

请判断：是否存在某种操作序列，使得该蛇能够完成翻转。

The first line contains a single integer $t$ ($1\le t\le 100$) — the number of test cases. The next lines contain descriptions of test cases.

The first line of each test case contains three integers $n,a,b$ ($2\le n\le 10^5,1\le a,b\le n,a\ne b$).

Each of the next $n-1$ lines contains two integers $u_i,v_i$ ($1\le u_i,v_i\le n,u_i\ne v_i$), indicating an edge between vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.

第一行包含一个整数 $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$。

For each test case, output "YES" if it is possible for the snake to reverse itself, or "NO" otherwise.

对于每个测试用例，如果蛇能够反转自身，则输出 “YES”，否则输出 “NO”。

The first test case is pictured above.

In the second test case, the tree is a path. We can show that the snake cannot reverse itself.

In the third test case, we can show that the snake cannot reverse itself.

In the fourth test case, an example solution is:

$(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)$.

第一个测试用例如上图所示。

在第二个测试用例中，该树是一条路径。我们可以证明蛇无法反转自身。

在第三个测试用例中，我们可以证明蛇无法反转自身。

在第四个测试用例中，一个可行的解为：

$(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)$。