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:
#pragma GCC optimize("Ofast", "unroll-loops", "no-stack-protector")
 
#include <bits/stdc++.h>
 
using namespace std;

#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()

using ll = long long;
using ld = long double; 
// using ld = __float128;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using uint = unsigned int;
using ull = unsigned long long;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
default_random_engine generator;

void solve();

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout); 
#endif 

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << setprecision(10) << fixed;
    cerr << setprecision(10) << fixed;

    int tests = 1;
    // cin >> tests;

    for (int test = 1; test <= tests; ++test) {
        // cout << "Case #" << test << ": ";
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << double(clock()) / CLOCKS_PER_SEC << endl;
#endif
}

// ----------------------------------------------------------------- 

const int MAXN = 200200;
vector<int> g[MAXN];
int w[MAXN];

vector<int> arr;
int dfs(int v, int p = -1) {
    arr.push_back(v);
    w[v] = 1;
    for (int u : g[v]) {
        if (u == p) {
            continue;
        }
        w[v] += dfs(u, v);
    }
    return w[v];
}

vector<int> f;

bool check(int root, int k) {
    arr.clear();
    dfs(root);
    if (sz(arr) != f[k]) {
        return false;
    }
    if (k <= 1) {
        return true;
    }

    for (int v : arr) {
        if (w[v] == f[k - 1] || w[v] == f[k - 2]) {
            int u;
            for (int uu : g[v]) {
                if (w[uu] > w[v]) {
                    u = uu;
                }
            }

            for (int i = 0; i < sz(g[u]); ++i) {
                if (g[u][i] == v) {
                    swap(g[u][i], g[u].back());
                    g[u].pop_back();
                    break;
                }
            }
            for (int i = 0; i < sz(g[v]); ++i) {
                if (g[v][i] == u) {
                    swap(g[v][i], g[v].back());
                    g[v].pop_back();
                    break;
                }
            }

            if (w[v] == f[k - 1]) {
                if (!check(v, k - 1)) {
                    return false;
                }
                if (!check(u, k - 2)) {
                    return false;
                }
            } else {
                if (!check(v, k - 2)) {
                    return false;
                }
                if (!check(u, k - 1)) {
                    return false;
                }
            }
            return true;
        }
    }
    return false;
}

void solve() {  
    int n;
    cin >> n;

    int k = 2;
    f = {1, 1};
    for (; f.back() < n; ++k) {
        f.push_back(f[k - 2] + f[k - 1]);
    }

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    cout << (check(0, sz(f) - 1) ? "YES\n" : "NO\n");
}