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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define forq(i , a , b) for (int i = (a); i <= (b); ++i)
#define qrof(i , b , a) for (int i = (a); i >= (b); --i)
#define forr(i , b) forq( i , 0 , b - 1 )
#define F first
#define S second
#define IF ->first
#define IS ->second
#define endl '\n'
#define qqmemset(array , val) memset (array , val , sizeof(array))
#define ALLV(vect) vect.begin() , vect.end()
#define mid (st + en) / 2
#define mid1 (2 * st + en) / 3
#define mid2 (2 * en + st) / 3
#define lef 2 * Node
#define rig lef + 1
mt19937 rng( chrono::steady_clock::now().time_since_epoch().count() );
#define Ran(a, b) rng() % ( (b) - (a) + 1 ) + (a)

ll R = 7 + 1e9 , R1 = 19491001 , R2 = 236 , NUMTESTCASE ;
const ll NN = 10 + 1e6 ;
const double pi = acos(-1.0) ;
int di [8] = {1 , 0 , -1 , 0  , 1 , -1 , 1  , -1 } , dj [8] = {0 , 1 , 0  , -1 , 1 , -1 , -1 , 1  } ;
int Fib [52] , n , u , v , Nodes [NN] , Parent [NN] ;
int Fibo [NN] ;
bool Forb [NN] ;
vector <int> G [NN] ;

void Dfs (int Ver , int Par) {
    Parent [Ver] = Par ;
    Nodes [Ver] = 1 ;
    for (int u : G [Ver])
        if (u ^ Par)
            Dfs(u , Ver) , Nodes [Ver] += Nodes [u] ;
}

int Cut (int Ver , int Tar1 , int Tar2) {
    
    if (Nodes [Ver] == Tar1 || Nodes [Ver] == Tar2)
        return Ver ;
    
    int Res ;
    for (int u : G [Ver])
        if (u ^ Parent [Ver])
            if (!Forb [u])
                if (Res = Cut(u , Tar1 , Tar2))
                    return Res ;

    return 0 ;
}

bool Check (int Ver) {

    if (Nodes [Ver] <= 2)
        return true ;

    if (!Fibo [Nodes [Ver]]) return false ;


    int u = Cut(Ver , Fib [Fibo [Nodes [Ver]] - 1] , Fib [Fibo [Nodes [Ver]] - 2]) ;

    int x = Nodes [u] ;
    if (!Check(u) || !u)
        return false ;

    Forb [u] = true ;

    for (int v = Parent [u] ; v != Ver ; v = Parent [v])
        Nodes [v] -= x ;

    Nodes [Ver] -= x;

    return Check(Ver) ;
}
int main()
{
    Fib [1] = 1 ;
    for (int n = 2 ; n <= 28 ; n ++)
        Fib [n] = Fib [n - 1] + Fib [n - 2] ;
    for (int i = 1 ; i <= 32 ; i ++)
        Fibo [Fib [i]] = i ;
    
    cin >> n ;
    forq (i , 2 , n) {
        scanf("%d%d" , &u , &v) ;
        G [u].pb (v) ;
        G [v].pb (u) ;
    }

    Dfs(1 , 1) ;

    cout << (Check(1) ? "YES\n" : "NO\n") ;
    return 0;
}