F. Вишнёвое дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано корневое дерево на $$$n$$$ вершинах$$$^{\text{∗}}$$$. Вершины дерева пронумерованы целыми числами от $$$1$$$ до $$$n$$$. Корнем дерева является вершина номер $$$1$$$.

В каждом листе$$$^{\text{†}}$$$ дерева растёт по одной вишне. Вы хотите собрать всю вишню, для этого несколько раз вы делаете следующее:

Вы выбираете любую вершину дерева $$$v$$$ (в том числе можно выбрать корень или лист) и «трясёте» за неё. После этого из всех листьев, которые являются потомками$$$^{\text{‡}}$$$ вершины $$$v$$$, падает вишня (если вершина $$$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$$$.

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

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

Вы можете выводить каждую букву в любом регистре (нижнем или верхнем). Например, «YeS», «no» и «yES» являются корректными ответами.

Пример
Входные данные
3
4
1 2
1 3
1 4
3
1 2
1 3
9
1 2
3 1
2 4
5 2
5 6
3 7
8 3
8 9
Выходные данные
YES
NO
YES
Примечание

В первом наборе входных данных можно потрясти за вершины $$$2, 3, 4$$$.

Во втором наборе входных данных единственный способ потрясти количество вершин, кратное трём — потрясти за все вершины. Но тогда дерево сломается, поэтому так делать нельзя.

В третьем наборе входных данных можно, например, потрясти за вершины $$$2, 7, 9$$$.