CF2184F.Cherry Tree

You are given a rooted tree with $n$ vertices$^{\text{∗}}$. The vertices of the tree are numbered with integers from $1$ to $n$. The root of the tree is vertex number $1$.

In each leaf$^{\text{†}}$ of the tree, there grows one cherry. You want to collect all the cherries, and to do this, you perform the following action several times:

You choose any vertex of the tree $v$ (including the root or a leaf) and "shake" it. After that, cherries fall from all the leaves that are descendants$^{\text{‡}}$ of vertex $v$ (if vertex $v$ itself is a leaf, then a cherry falls from it). If cherries have already fallen from any leaf before, the tree will break, so such a situation must be avoided.

According to an ancient legend of the cherry orchard, the number of vertices you shake should be a multiple of three.

Is it possible to collect all the cherries in this way?

$^{\text{∗}}$A tree with $n$ vertices is an undirected connected graph with $n$ vertices and $n - 1$ edges. A rooted tree is a tree in which one of the vertices is special and is called the root.

$^{\text{†}}$A leaf is a vertex that has no descendants.

$^{\text{‡}}$The descendants of vertex $v$ are all vertices $u \neq v$ such that on the shortest path from the root to $u$, vertex $v$ is encountered.

你被给定一棵有 $n$ 个顶点的有根树$^{\text{∗}}$。树的顶点用 $1$ 到 $n$ 的整数编号，树的根为顶点 $1$。

树的每个叶节点$^{\text{†}}$ 上都长有一颗樱桃。你想收集所有樱桃，为此你需要重复执行以下操作若干次：

你任选树中的一个顶点 $v$（可以是根节点或叶节点）并“摇晃”它。此后，所有以顶点 $v$ 为祖先的叶节点上的樱桃都会掉落（若 $v$ 本身是叶节点，则它上面的樱桃也会掉落）。如果某叶节点上的樱桃此前已经掉落过，则树会损坏，因此必须避免这种情况。

根据樱桃果园的古老传说，你所摇晃的顶点总数必须是 $3$ 的倍数。

能否以这种方式收集全部樱桃？

$^{\text{∗}}$ 一棵含 $n$ 个顶点的树是一个具有 $n$ 个顶点和 $n - 1$ 条边的无向连通图；有根树是一棵指定其中一个顶点为根的树。

$^{\text{†}}$ 叶节点是指没有子节点的顶点。

$^{\text{‡}}$ 顶点 $v$ 的后代是指所有满足 $u \neq v$ 的顶点 $u$，且在从根到 $u$ 的最短路径上经过顶点 $v$。

Each test consists of several test cases. The first line contains a single integer $t$ $(1 \le t \le 10^4)$ — the number of test cases. The following lines describe the test cases.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$).

The next $n - 1$ lines of each test case contain two integers $u$ and $v$ ($1 \leq u, v \leq n, u \neq v$) — the vertices connected by the next edge of the tree.

It is guaranteed that the graph in each data set is a tree.

It is guaranteed that the sum of $n$ across all input data sets does not exceed $2 \cdot 10^5$.

每个测试包含若干个测试用例。第一行包含一个整数 $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$。

For each input data set, output "YES" on a separate line if it is possible to collect all the cherries. Otherwise, output "NO".

You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.

对于每组输入数据，如果能够收集到所有樱桃，则在单独一行输出“YES”；否则输出“NO”。

每个字母可以以任意大小写形式输出（大写或小写）。例如，“YeS”、“no”和“yES”都是可接受的。

In the first test case, you can shake vertices $2, 3, 4$.

In the second test case, the only way to shake a number of vertices that is a multiple of three is to shake all the vertices. However, doing so would break the tree, so this is not allowed.

In the third test case, you can, for example, shake vertices $2, 7, 9$.

在第一个测试用例中，你可以摇动顶点 $2, 3, 4$。

在第二个测试用例中，唯一能使被摇动顶点数量为 $3$ 的倍数的方式是摇动所有顶点。然而，这样做会使树断裂，因此这是不允许的。

在第三个测试用例中，例如，你可以摇动顶点 $2, 7, 9$。