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

  * F_0 = F_1 = 1
  * for any integer n ≥ 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 ≤ n ≤ 2 ⋅ 10^5) — the number of vertices in the tree.

Then n-1 lines follow, each of which contains two integers u and v (1≤ u,v ≤ n, u ≠ 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). 

Solution (in PYTHON3):

Solution:
import sys

sys.setrecursionlimit(10**5)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.buffer.readline())
def MI(): return map(int, sys.stdin.buffer.readline().split())
def MI1(): return map(int1, sys.stdin.buffer.readline().split())
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def BI(): return sys.stdin.buffer.readline().rstrip()
def SI(): return sys.stdin.buffer.readline().rstrip().decode()
inf = 10**16
md = 10**9+7
# md = 998244353

fibo = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657,
        46368, 75025, 121393, 196418]
ftoi = {f: i for i, f in enumerate(fibo)}

n = II()
to = [[] for _ in range(n)]
for e in range(n-1):
    u, v = MI1()
    to[u].append(v)
    to[v].append(u)

if n <= 3:
    print("YES")
    exit()

if n not in ftoi:
    print("NO")
    exit()

stack = [0]
sz = [-1]*n
par = [-1]*n
while stack:
    u = stack.pop()
    if sz[u] == -1:
        sz[u] = 1
        stack.append(u)
        for v in to[u]:
            if v == par[u]: continue
            par[v] = u
            stack.append(v)
    else:
        sz[par[u]] += sz[u]
# print(sz, par)

fin = [False]*n

def dfs(r, s):
    i = ftoi[s]
    s1, s2 = fibo[i-1], fibo[i-2]
    stack = [r]
    while stack:
        u = stack.pop()
        for v in to[u]:
            if v == par[u]: continue
            if fin[v]: continue
            if sz[v] == s1 or sz[v] == s2:
                fin[v] = True
                return v
            stack.append(v)
    return -1

def ok():
    root = [(0, sz[0])]
    while root:
        r, s = root.pop()
        u = dfs(r, s)
        if u == -1: return False
        s1 = sz[u]
        if s1 > 3: root.append((u, s1))
        if s-s1 > 3: root.append((r, s-s1))
        while u != r:
            u = par[u]
            sz[u] -= s1
    return True

print("YES" if ok() else "NO")