E. Фиб-дерево
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$F_k$$$ обозначает $$$k$$$-й член последовательности Фибоначчи, определенной следующим образом:

  • $$$F_0 = F_1 = 1$$$
  • для любого целого $$$n \geq 0$$$, $$$F_{n+2} = F_{n+1} + F_n$$$.

Вам дано дерево с $$$n$$$ вершинами. Напомним, что дерево — это связный неориентированный граф без циклов.

Дерево называется Фиб-деревом, если его количество вершин равно $$$F_k$$$ для некоторого $$$k$$$, и выполняется хотя бы одно из следующих условий:

  • Дерево состоит только из $$$1$$$ вершины;
  • Вы можете разделить его на два Фиб-дерева, удалив некоторое ребро дерева.

Определите, является ли данное дерево Фиб-деревом.

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

В первой строке входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество вершин в дереве.

Далее следуют $$$n-1$$$ строк, каждая из которых содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1\leq u,v \leq n$$$, $$$u \neq v$$$), обозначающие ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что данные ребра образуют дерево.

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

Выведите «YES», если данное дерево является Фиб-деревом, или «NO», если не является.

Ответ можно вывести в любом регистре. Например, если ответ «YES», то вывод «Yes» или «yeS» также будет считаться правильным ответом.

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

В первом примере можно удалить ребро $$$(1, 2)$$$, и дерево будет разбито на $$$2$$$ дерева размера $$$1$$$ и $$$2$$$ соответственно. Любое дерево размера $$$2$$$ является Фиб-деревом, так как его можно разбить на $$$2$$$ дерева размером $$$1$$$.

Во втором примере, независимо от того, какое ребро мы удаляем, дерево будет разбито на $$$2$$$ дерева размера $$$1$$$ и $$$4$$$. Поскольку $$$4$$$ не равняется $$$F_k$$$ ни для какого $$$k$$$, это не Фиб-дерево.

В третьем примере, вот один из возможных порядков удаления ребер, чтобы все деревья в процессе были Фиб-деревьями: $$$(1, 3), (1, 2), (4, 5), (3, 4)$$$.