Пусть \(F_k\) обозначает \(k\)-й член последовательности Фибоначчи, определенной следующим образом:
- \(F_0 = F_1 = 1\)
- для любого целого \(n \geq 0\), \(F_{n+2} = F_{n+1} + F_n\).
Вам дано дерево с \(n\) вершинами. Напомним, что дерево — это связный неориентированный граф без циклов.
Дерево называется Фиб-деревом, если его количество вершин равно \(F_k\) для некоторого \(k\), и выполняется хотя бы одно из следующих условий:
- Дерево состоит только из \(1\) вершины;
- Вы можете разделить его на два Фиб-дерева, удалив некоторое ребро дерева.
Определите, является ли данное дерево Фиб-деревом.
Выходные данные
Выведите «YES», если данное дерево является Фиб-деревом, или «NO», если не является.
Ответ можно вывести в любом регистре. Например, если ответ «YES», то вывод «Yes» или «yeS» также будет считаться правильным ответом.
Примечание
В первом примере можно удалить ребро \((1, 2)\), и дерево будет разбито на \(2\) дерева размера \(1\) и \(2\) соответственно. Любое дерево размера \(2\) является Фиб-деревом, так как его можно разбить на \(2\) дерева размером \(1\).
Во втором примере, независимо от того, какое ребро мы удаляем, дерево будет разбито на \(2\) дерева размера \(1\) и \(4\). Поскольку \(4\) не равняется \(F_k\) ни для какого \(k\), это не Фиб-дерево.
В третьем примере, вот один из возможных порядков удаления ребер, чтобы все деревья в процессе были Фиб-деревьями: \((1, 3), (1, 2), (4, 5), (3, 4)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
2 3
|
YES
|
|
2
|
5
1 2
1 3
1 4
1 5
|
NO
|
|
3
|
5
1 3
1 2
4 5
3 4
|
YES
|