Codeforces Global Round 13 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

dfs and similar

divide and conquer

number theory

trees

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Fib-tree

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet $$$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.

Input

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.

Output

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.

Examples

Input

3 1 2 2 3

Output

YES

Input

5 1 2 1 3 1 4 1 5

Output

NO

Input

5 1 3 1 2 4 5 3 4

Output

YES

Note

In the first sample, we can cut the edge $$$(1, 2)$$$, and the tree will be split into $$$2$$$ trees of sizes $$$1$$$ and $$$2$$$ correspondently. Any tree of size $$$2$$$ is a Fib-tree, as it can be split into $$$2$$$ trees of size $$$1$$$.

In the second sample, no matter what edge we cut, the tree will be split into $$$2$$$ trees of sizes $$$1$$$ and $$$4$$$. As $$$4$$$ isn't $$$F_k$$$ for any $$$k$$$, it's not Fib-tree.

In the third sample, here is one possible order of cutting the edges so that all the trees in the process are Fib-trees: $$$(1, 3), (1, 2), (4, 5), (3, 4)$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2024 07:47:38 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|