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 endl '\n'
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define IO freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
#define P(x) cout<<x<<endl
#define P2(x,y) cout<<x<<' '<<y<<endl
#define P3(x,y,z) cout<<x<<' '<<y<<' '<<z<<endl
#define P4(x,y,z,u) cout<<x<<' '<<y<<' '<<z<<' '<<u<<endl
#define P5(x,y,z,u,v) cout<<x<<' '<<y<<' '<<z<<' '<<u<<' '<<v<<endl
#define P6(x,y,z,u,v,w) cout<<x<<' '<<y<<' '<<z<<' '<<u<<' '<<v<<' '<<w<<endl
#define PV(x) for(auto ii:(x)){cout<<ii<<' ';}cout<<endl
#define PN(x,n) for(int ii=1;ii<=(n);ii++){cout<<x[ii]<<' ';}cout<<endl
#define PNN(x,n,m) for(int ii=1;ii<=(n);ii++){for(int jj=1;jj<=(m);jj++){cout<<x[ii][jj]<<' ';}cout<<endl;}
typedef long long ll;
typedef unsigned long long ull;
const ll D = 0;
const ll N = 2e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
const double eps = 1e-9;

ll n,u,v;
struct Node
{
    ll id;
    bool ok;
};
vector<Node> g[N];
ll fib[60];
bool is_fib[N];
ll child[N];

void dfs(ll now,ll fa,ll siz,ll* uu,ll* vv)//find child[],father[];
{
    if(D)
    {
      //  P2(now,fa);
    }
   // if((*uu)!=-1)
       // return;
    child[now]=0;
    for(Node nxt : g[now])
    {
        if(D)
        {
           // P2("size ",g[now].size());
        }
        if(nxt.ok && nxt.id!=fa)
        {
            if(D)
            {
                //P5(now,fa,"to",nxt.id,now);
            }
            dfs(nxt.id,now,siz,uu,vv);
            child[now] += child[nxt.id];
            
        }
    }
    child[now]++;
    if(now!=fa && is_fib[child[now]] && is_fib[siz - child[now]])
    {
        *uu=now;
        *vv=fa;
    }
	return;
}
bool check(ll now,ll siz)
{
   // ll child[N];
    //memset(child,0,sizeof(child));
    if(siz==1)
        return true;
    ll uu=-1,vv=-1;
    dfs(now,now,siz,&uu,&vv);
    if(D)
    {
        PN(child,n);
    }
    
    if(D)
    {
        P4("find",uu,vv,siz);
    }
    
    if(!is_fib[siz])
        return false;
    if(uu==-1 || vv==-1)
        return false;
    for(Node &nxt : g[uu])
    {
        if(nxt.id == vv)
        {
            nxt.ok = false;
            break;
        }
    }
    for(Node &nxt : g[vv])
    {
        if(nxt.id == uu)
        {
            nxt.ok = false;
            break;
        }
    }
     if(D)
    {
        P6(now,"to",uu,vv,"in",siz);
        
    }
    ll siz2 = child[uu];
    bool res = check(uu,siz2) && check(vv,siz - siz2);//fa
    for(Node &nxt : g[uu])
    {
        if(nxt.id == vv)
        {
            nxt.ok = true;
            break;
        }
    }
    for(Node &nxt : g[vv])
    {
        if(nxt.id == uu)
        {
            nxt.ok = true;
            break;
        }
    }
    return res;
}

int solve()
{
    fib[0]=fib[1]=1;
    is_fib[1]=true;
    for(ll i=2;;i++)
    {
        fib[i] = fib[i-1] + fib[i-2];
        if(fib[i]>2e5)
            break;
        is_fib[fib[i]] = true;
    }

	cin>>n;
    
    for(ll i=1;i<=n-1;i++)
    {
        cin>>u>>v;
        g[u].push_back({v,true});
        g[v].push_back({u,true});
    }
    //u = v = -1;
    
    cout<<(check(1,n)?"YES\n":"NO\n");
	return 0;
}

int main()
{
	//BUFF;
	if(D)IO;
	ll t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}