Киду подарили дерево из \(n\) вершин с корнем в вершине \(1\). Так как он очень любит симметричные объекты, Кид хочет узнать симметрично ли это дерево.
Например, деревья на картинке выше симметричны. 
А деревья на этой картинке не симметричны. Более формально, дерево является симметричным, если существует такой порядок детей, что:
- Поддерево самого левого ребёнка корня является зеркальным отражением поддерева самого правого ребёнка;
- поддерево второго слева ребёнка корня является зеркальным отражением поддерева второго справа ребёнка корня;
- ...
- если число детей корня нечётно, то поддерево среднего ребёнка должно быть симметрично.
Выходные данные
Выведите \(t\) строк, каждая из которых является ответом на соответствующий набор входных данных. В качестве ответа выведите «YES», если данное дерево симметрично, и «NO» в противном случае.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|