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 rep(i, n) for(int i = 0; i < n; i++)
#define pb push_back
#define debug(x) cout << #x << " " << x << endl
#define all(x) x.begin(),x.end()
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vll vector<ll>
#define vvll vector<vll>
#define ld long double
#define ull unsigned long long
#define vull vector<ull>
#define fi first
#define se second
#define PII pair<int,int>
#define vPII vector<PII>

int out = 0;
vi adj[200005];
int ok = 0;
vi granica(200005,0);
//int dfs(int cur, int par, int pop1,int pop2){
//    int out_start = out;
//    for(int nxt: adj[cur]){
//        if(nxt != par and !granica.count(nxt)){
//            dfs(nxt,cur,pop1,pop2);
//            if(out-out_start == pop1 or out_start == pop2){
//                int ile = out - out_start;
//                granica.insert(cur);
//                if(dfs(nxt,cur,pop2,pop1-pop2)){
//                    granica.erase(cur);
//                    granica.insert(nxt);
//                    if(dfs(cur,nxt,pop))
//                }
//            }
//        }
//    }
//    out++;
//}
int dfs(int cur, int par, int pop1,int pop2){
    int out_start = out;
    int licz = 0;
    for(int nxt: adj[cur]){
        if(nxt!=par and !granica[nxt]){
            licz++;
            if(dfs(nxt,cur,pop1,pop2)) return 1;
            int out_pom = out;
            if(out - out_start == pop1 or out - out_start == pop2){
                int ile = out - out_start;
                int j,d,t,c;
                if(ile == pop1){
                    j = pop2;
                    d = pop1-pop2;
                    t = pop1- pop2;
                    c = pop2 - t;
                }else{
                    j = pop1-pop2;
                    d = pop2 - j;
                    t = pop2;
                    c = pop1 - pop2;
                }
                granica[cur] = 1;
                if(dfs(nxt,cur,j,d)){
                    granica[cur] = 0;
                    granica[nxt] = 1;
                    if(dfs(cur,nxt,t,c)){
                        granica[nxt] = 0;
                        out = out_pom;
                        return 1;
                    }
                }
                granica[cur] = 0;
                granica[nxt] = 0;
            }
            out = out_pom;
            out_start = out;
        }
    }
    out++;
    if(licz == 0 and (pop1 == 1 or pop2 == 1)) return 1;
    return 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //cout << setprecision(8) << fixed;
    int t = 1;
    //cin >> t;
    while(t--){
        int n;
        cin >> n;
        rep(i,n-1){
            int u,v;
            cin >> u >> v;
            u--;v--;
            adj[u].pb(v);
            adj[v].pb(u);
        }
        int a = 1,b = 1;
        while(b != n and b <= n){
            int pom = b;
            b = a+b;
            a = pom;
        }
        if(n==1){
            cout << "YES\n";
            return 0;
        }
        if(b != n){
            cout << "NO\n";
            return 0;
        }
        int pop1,pop2;
        pop1 = a;
        pop2 = b - a;
        //dfs(0,-1,pop1,pop2);
        if(dfs(0,-1,pop1,pop2)) cout << "YES\n";
        else cout << "NO\n";
    }
}