Киду подарили дерево из \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач