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 <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define pb push_back
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a) memset(a, 0, sizeof(a))
#define LP pair<ll, int>
#define LPP pair<LP, int>
#define LPPP pair<LPP, int>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
typedef double db;
typedef pair<int, int> P;
const int maxn = 2e5 + 10;
int t, n, vis[maxn], fib[maxn], sz[maxn], ok = 1;
vector<P> ns[maxn];
void setSize(int u, int fa){
    sz[u] = 1;
    for(pair<int, bool> e : ns[u])
    {
        if(!e.second) continue;
        int v = e.first;
        if(v == fa) continue;
        setSize(v, u);
        sz[u] += sz[v];
    }
}
void cut(int u, int fa, int k, int& nu, int &nv, int &sta){
    for (auto tmp : ns[u]) {
        if(sta) return;
        if(!tmp.second) continue;
        int vv = tmp.first;
        if(vv == fa) continue;
        if(sz[vv] == fib[k - 1] || sz[vv] == fib[k - 2]){
            nu = u, nv = vv, sta = (sz[vv] == fib[k - 1]) ? k - 1 : k - 2;
            break;
        }
        cut(vv,  u, k, nu, nv, sta);
    }
}
void check(int u, int val){//check as fa = u, has fib[val] nodes
    if(fib[val] <= 1) return;
    setSize(u, 0);
    int pv = 0, kd = 0,pu = 0;
    cut(u, 0, val, pu, pv, kd);
//    if(n == 121393 || n == 196418) return;
 
    if(kd == 0) {
        ok = 0;
        printf("NO\n");
        exit(0);
    }
    for (auto &tmp : ns[pv]) if(tmp.first == pu) tmp.second = 0;//make as a visit
    for (auto &tmp : ns[pu]) if(tmp.first == pv) tmp.second = 0;
    check(pv, kd);
    check(pu, (kd == val - 1) ? val - 2 : val - 1);
}
 
int main(){
//    freopen("1.in", "w", stdout);
//    printf("200000\n");
//    for (int i = 1; i < 196418; ++i) {
//        printf("%d %d\n", i, i + 1);
//    }
//    return 0;
//    freopen("1.in", "r", stdin);
    mem(fib), mem(vis);
    int u, v;
    fib[1] = fib[2] = 1, t = 3, u = 2, vis[1] = 1;
    while (u < maxn) vis[u] = t, fib[t] = u, u = fib[t - 1] + fib[t], t++;
 
    scanf("%d", &n);
    if(!vis[n]) {
        printf("NO\n");
        return 0;
    }
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        ns[u].push_back(make_pair(v, 1)), ns[v].push_back(make_pair(u, 1));
    }
    check(1, vis[n]);
    printf("%s\n", ok ? "YES" : "NO");
}