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>
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,a,n) for(int i=n;i>=a;--i)
#define mst(x) memset(x,0,sizeof(x));
#define n_p(a,n) next_permutation(a,a+n)
#define yx_queue priority_queue
#define PI acos(-1)
#define see(x) cerr<<(#x)<<'='<<(x)<<endl
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef double db;
typedef unsigned __int128 ulll;
typedef unsigned long long ull;
typedef long long ll;
const ll mod=( 0 ?998244353:1000000007);
const int inf=1<<30;
const ll llf=9e18;
ll powmod(ll a,ll b,ll pp=mod) {ll res=1;a%=pp;assert(b>=0);for(;b;b>>=1,a=a*a%pp)if(b&1)res=res*a%pp;return res;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll mul(ll a,ll b,ll pp=mod) {ll ans=0;for(;b;b>>=1){if(b&1)ans=(ans+a)%pp;a=a*2%pp;}return ans;}//快速乘避免爆ll 
struct node{
    int x,y,z,time;
    ll no,w,h;
    int pre,nxt;
    friend bool operator<(const node&a,const node&b)
    {
        return a.x<b.x||(a.x==b.x&&a.y<b.y);//sort时<小的在前 优先队列时>小的在前 
    }
};
bool cmp(int x,int y)
{
    return x>y;
}
//unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
//mt19937 myrand(seed);
//uniform_int_distribution<ll>dist(1,100);//设定随机范围;
// dist(myrand); 这就是个在范围内的随机数; 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//shuffle(a+1,a+n+1,rng);//随机打乱数组 
//prev_permutation(a+1,a+n+1);上一个排列 
//next_permutation(a+1,a+n+1);下一个排列 
inline int min(int a,int b){if(a>b)return b;else return a;}
inline int max(int a,int b){if(a<b)return b;else return a;}
inline void upmax(int& a,int b){if(a<b)a=b;};
inline void upmin(int& a,int b){if(a>b)a=b;};
//inline void read(__int128 &X){X = 0;int w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();if (w) X = -X;}
template<class T>inline void pt(T x){
	static int top,stk[105];
	if(x<0)x=-x,putchar('-');
	if(x==0)putchar('0');
	while(x)stk[++top]=x%10,x/=10;
	while(top)putchar(stk[top--]+'0');
}
//区间更新树状数组,bit1是b[i]的前缀和,bit2是b[i]*i的前缀和,b是a的差分数组 
//void add(ll *bit,int x,ll v){while(x<=n)bit[x]+=v,x+=x&-x;}
//ll query(ll *bit,int x){ll res=0;while(x)res+=bit[x],x-=x&-x;return res;}
//void interval_add(ll *bit1,ll *bit2,int l,int r,ll v){add(bit1,l,v);add(bit2,l,v*l);add(bit1,r+1,-v);add(bit2,r+1,-v*(r+1));}
//ll interval_query(ll *bit1,ll *bit2,int l,int r){return (r+1)*query(bit1,r)-query(bit2,r)-l*query(bit1,l-1)+query(bit2,l-1);}
//并查集 
//int f[200100];
//int find(int x){ return x==f[x] ? x : f[x] = find(f[x]); }
//ST表 
//int f[200010][21];
//int query(int l,int r){int k=log2(r-l+1); return max(f[l][k],f[r-(1<<k)+1][k]);}
//void st(int a){for(int i=1;i<=21;i++)for(int j=1;j+(1<<i)-1<=a;j++)f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);}
//组合数
//const ll maxn=2001000;
//ll fac[maxn];
//void cinit(){fac[0]=1;for(int i=1;i<maxn;i++)fac[i]=fac[i-1]*i%mod;}
//ll C(ll x, ll y){if(x<y)return 0;return fac[x]*powmod(fac[y]*fac[x-y]%mod,mod-2)%mod;}//x>y
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,-1,1,1,-1};
const int N=200005;
const db eps=1e-12;
//while(rp++)

VI g[200100];
VI id[200100];
int f[100]; 
int sum[200100];
int faline[200100];
int line[201000];
bool dfs(int now,int n,int fa)
{
	if(n<=3)return true;
	sum[now]=1;
	rep(i,0,g[now].size()-1)
	{
		int to=g[now][i];
		if(to==fa)continue;
		if(line[id[now][i]])continue;
		faline[to]=id[now][i];
		if(dfs(to,n,now))return true;
		sum[now]+=sum[to];
	}
	int h=n-2;
	if(sum[now]==f[h]||sum[now]==f[h+1])
	{
		line[faline[now]]=1;
		if(sum[now]==f[h]&&dfs(now,h,now)&&dfs(fa,h+1,fa))return true;
		else if(sum[now]==f[h+1]&&dfs(now,h+1,now)&&dfs(fa,h,fa))return true;
		line[faline[now]]=0;
	}
	return false; 
 }
signed main()
{
    ios::sync_with_stdio(false);
    //freopen("a.in","r",stdin);
    //freopen("aa.txt","w",stdout); 
    int _=1;
	//cin>>_;
	f[0]=f[1]=1;
	rep(i,2,30)f[i]=f[i-1]+f[i-2];
    while(_--)
    {
    	int u,v,n;
    	cin>>n;
		int cnt=0; 
    	rep(i,1,n-1)
		{
			cin>>u>>v;
			g[u].pb(v);
			g[v].pb(u);
			++cnt;
			id[u].pb(cnt);
			id[v].pb(cnt);
		} 
		if(*lower_bound(f+1,f+31,n)!=n)return cout<<"NO",0;
		if(dfs(1,lower_bound(f+1,f+31,n)-f,1))cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}