G. Симмеtreeя
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Киду подарили дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$. Так как он очень любит симметричные объекты, Кид хочет узнать симметрично ли это дерево.

Например, деревья на картинке выше симметричны.
А деревья на этой картинке не симметричны.

Более формально, дерево является симметричным, если существует такой порядок детей, что:

  • Поддерево самого левого ребёнка корня является зеркальным отражением поддерева самого правого ребёнка;
  • поддерево второго слева ребёнка корня является зеркальным отражением поддерева второго справа ребёнка корня;
  • ...
  • если число детей корня нечётно, то поддерево среднего ребёнка должно быть симметрично.
Входные данные

Первая строка входных данных содержит единственное число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Следующие $$$n-1$$$ строк содержат по два числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — номера вершин, соединённых ребром.

Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.

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

Выведите $$$t$$$ строк, каждая из которых является ответом на соответствующий набор входных данных. В качестве ответа выведите «YES», если данное дерево симметрично, и «NO» в противном случае.

Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

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