A14112 | Fib-tree

Let $F_k$ denote the $k$ -th term of Fibonacci sequence, defined as below:

- $F_0 = F_1 = 1$
- for any integer $n \geq 0$ , $F_{n+2} = F_{n+1} + F_n$

You are given a tree with $n$ vertices. Recall that a tree is a connected undirected graph without cycles.

We call a tree a Fib-tree, if its number of vertices equals $F_k$ for some $k$ , and at least one of the following conditions holds:

- The tree consists of only $1$ vertex;
- You can divide it into two Fib-trees by removing some edge of the tree.

Determine whether the given tree is a Fib-tree or not.

The first line of the input contains a single integer $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) — the number of vertices in the tree.

Then $n-1$ lines follow, each of which contains two integers $u$ and $v$ ( $1\leq u,v \leq n$ , $u \neq v$ ), representing an edge between vertices $u$ and $v$ . It's guaranteed that given edges form a tree.

Print "YES" if the given tree is a Fib-tree, or "NO" otherwise.

You can print your answer in any case. For example, if the answer is "YES", then the output "Yes" or "yeS" will also be considered as correct answer.