有一个由 $$$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”。
示例
输入 #1
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
输出 #1
YES NO NO YES
注意
第一个测试用例如上图所示。
在第二个测试用例中,树是一条路径。我们可以证明蛇不能逆转自己。
在第三个测试用例中,我们可以证明蛇无法反转自身。
在第四个测试用例中,示例解决方案是:
$$$(15,12)\至(16,11)\至(15,13)\至(10,14)\至(8,13)\至(4,11)\至(1,10)$$$
$$$\到(2,8)\到(3,4)\到(2,5)\到(1,6)\到(4,7)\到(8,6)\到(10,5)$$$
$$$\到(11,4)\到(13,8)\到(14,10)\到(13,15)\到(11,16)\到(12,15)$$$。