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:
"""
#If FastIO not needed, use this and don't forget to strip
#import sys, math
#input = sys.stdin.readline
"""

import os, sys, heapq as h, time
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict as dd
import math, string
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

#start_time = time.time()

def getInt(): return int(input())
def getStrs(): return input().split()
def getInts(): return list(map(int,input().split()))
def getStr(): return input()
def listStr(): return list(input())
def getMat(n): return [getInts() for _ in range(n)]
def isInt(s): return '0' <= s[0] <= '9'


"""
We need to find a reference point from which, for some node, the size of its sub tree if Fn-1 (then the other sub tree must be Fn-2

Can we isolate two trees of the right size, AND for which their sub trees work?

If it's a Fib tree, we must be able to root it at some vertex such that every node with children has one or two, all 

If N <= 3, done
Otherwise
Need to find subtrees of all Fib numbers <= 3
"""

def solve():
    N = getInt()
    fibs = [1,1]
    while True:
        x = fibs[-1]+fibs[-2]
        if x > N: break
        fibs.append(x)
    G = [[] for i in range(N)]
    for n in range(N-1):
        U, V = getInts()
        U -= 1
        V -= 1
        G[U].append(V)
        G[V].append(U)
    q = [(0,-1)]
    graph = [[] for i in range(N)]
    while q:
        v, p = q.pop()
        for neigh in G[v]:
            if neigh != p:
                graph[v].append(neigh)
                q.append((neigh,v))
    if fibs[-1] != N: return "NO"
    Q = [(0,len(fibs)-1)]
    subtree = [1]*N
    used = [False]*N
    while Q:
        node, idx = Q.pop()
        if idx <= 3: continue
        f1, f2 = fibs[idx-1], fibs[idx-2]
        q = [node]
        path = []
        while q:
            v = q.pop()
            subtree[v] = 1
            for neigh in graph[v]:
                if used[neigh]: continue
                path.append((v,neigh))
                q.append(neigh)
        for v, neigh in reversed(path):
            if subtree[neigh] in [f1,f2]:
                break
            subtree[v] += subtree[neigh]
        else:
            return "NO"
        used[neigh] = True
        if subtree[neigh] == f1:
            Q.append((neigh,idx-1))
            Q.append((node,idx-2))
        else:
            Q.append((neigh,idx-2))
            Q.append((node,idx-1))
    return "YES"
    
    
    
#for _ in range(getInt()):
print(solve())
#solve()

#print(time.time()-start_time)