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;

struct Edge{
    int to, nxt, ind;
    Edge() {}
};

struct EDGE{
    int u, v;
    EDGE() {}
};

const int MAX_N = 2e5 + 7;

Edge e[MAX_N << 1];
EDGE E[MAX_N];
int f[33] = {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};
int head[MAX_N], siz[MAX_N], color[MAX_N];
bool vis[MAX_N];
int n, cnt, num;

void add(int u, int v, int ind) {
   e[++cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt; e[cnt].ind = ind;
}

int get_size(int u, int fa) {
    int res = 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fa || vis[e[i].ind]) continue;
        res += get_size(v, u);
    }
    return res;
}

void dfs(int u, int fa, int ind, int k, int &flag) {
    if (k <= 1) return;
    siz[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fa || vis[e[i].ind]) continue;
        dfs(v, u, e[i].ind, k, flag);
        siz[u] += siz[v];
    }
    // printf("# %d: %d #\n", u, siz[u]);
    if (siz[u] == f[k - 2]) flag = ind;
    else if (siz[u] == f[k - 1]) flag = ind;
}

int find(int n) {
    for (int i = 1; i < 33; ++i) {
        if (f[i] == n) return i;
    }
    return 0;
}

void DFS(int u, int fa, int ind) {
    int size = get_size(u, fa);
    if (size <= 1) return;
    // printf("%d ", size);
    int flag = 0;
    dfs(u, fa, ind, find(size), flag);
    // printf("%d: (%d, %d)\n", flag, E[flag].u, E[flag].v);
    if (flag) {
        int x = E[flag].u, y = E[flag].v;
        vis[flag] = true;
        ++num;
        DFS(x, y, flag);
        DFS(y, x, flag);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v, i); add(v, u, i);
        E[i].u = u, E[i].v = v;
    }
    int k = find(n);
    // cout << k << endl;
    if (k) {
        DFS(1, 0, 0);
        if (num == n - 1) puts("YES");
        else puts("NO");
    } else {
        puts("NO");
    }
    return 0;
}