给你一棵有 $$$n$$$ 顶点 $$$^{\text{*}}$$$ 的有根树。树的顶点用从 $$$1$$$ 到 $$$n$$$ 的整数进行编号。树的根是顶点号$$$1$$$。
树的每片叶子$$$^{\text{†}}$$$中,都生长着一颗樱桃。您想要收集所有樱桃,为此,您需要执行以下操作多次:
你选择树 $$$v$$$ 的任意顶点(包括根或叶子)并“摇动”它。之后,樱桃会从顶点 $$$v$$$ 的后代 $$$^{\text{‡}}$$$ 的所有叶子上落下(如果顶点 $$$v$$$ 本身是一片叶子,那么樱桃就会从它落下)。如果樱桃已经从任何叶子上掉落,树就会折断,因此必须避免这种情况。
根据樱桃园的一个古老传说,摇动的顶点数量应该是三的倍数。
这样可以收集到所有的樱桃吗?
$$$^{\text{*}}$$$具有 $$$n$$$ 个顶点的树是具有 $$$n$$$ 个顶点和 $$$n - 1$$$ 个边的无向连通图。有根树是其中一个顶点是特殊的并称为根的树。
$$$^{\text{†}}$$$叶子是没有后代的顶点。
$$$^{\text{‡}}$$$顶点$$$v$$$的后代都是顶点$$$u \neq v$$$,这样在从根到$$$u$$$的最短路径上,会遇到顶点$$$v$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。以下几行描述了测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$)。
每个测试用例接下来的 $$$n - 1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n, u \neq v$$$) - 由树的下一条边连接的顶点。
保证每个数据集中的图都是一棵树。
保证所有输入数据集的 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个输入数据集,输出“是“如果可以收集所有樱桃,则在单独的行上。否则,输出“NO".
您可以以任何大小写(大写或小写)打印每个字母。例如,“是的", "no“和”是”都可以接受。
示例
输入复制
341 21 31 431 21 391 23 12 45 25 63 78 38 9
输出复制
YESNOYES
注意
在第一个测试用例中,您可以摇动顶点 $$$2, 3, 4$$$。
在第二个测试用例中,摇动三倍数顶点的唯一方法是摇动所有顶点。然而,这样做会破坏树,所以这是不允许的。
在第三个测试用例中,例如,您可以摇动顶点 $$$2, 7, 9$$$。