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>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk make_pair
#define pb push_back
#define eb emplace_back
#define ins insert
#define fi first
#define se second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXN=2e5+5;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}
int n,f[MAXN],tot,p[MAXN];
vector<vector<int> >G;
int sz[MAXN],dfn[MAXN],ed[MAXN],tim;
inline void dfs(int x,int fa,vector<vector<int> >&G){
	sz[x]=1,dfn[x]=++tim;
	for(auto y:G[x])if(y!=fa)dfs(y,x,G),sz[x]+=sz[y];
	ed[x]=tim;
}
inline bool check(vector<vector<int> >&G,int dep){
	if(dep<=3)return 1;int n=f[dep];tim=0,dfs(0,-1,G);
	Rep(i,0,n-1)if(sz[i]==f[dep-1]){
		vector<vector<int> >p1,p2;p1.clear(),p2.clear(),p1.resize(f[dep-1]),p2.resize(f[dep-2]);
		static int vis[MAXN],id[MAXN];int cnt=0,cnt1=0;
		Rep(j,0,n-1)if(dfn[j]>=dfn[i]&&dfn[j]<=ed[i])id[j]=cnt++,vis[j]=1;else id[j]=cnt1++,vis[j]=2;
		Rep(j,0,n-1)for(auto k:G[j])if(vis[j]==vis[k]){
			if(vis[j]==1)p1[id[j]].pb(id[k]);else p2[id[j]].pb(id[k]);
		}return check(p1,dep-1)&&check(p2,dep-2);
	}
	int cnt=0;
	Rep(i,0,n-1)if(sz[i]==f[dep-2])cnt++;
	if(cnt==1){
		Rep(i,1,n)if(sz[i]==f[dep-2]){
			vector<vector<int> >p1,p2;p1.clear(),p2.clear(),p1.resize(f[dep-2]),p2.resize(f[dep-1]);
			static int vis[MAXN],id[MAXN];int cnt=0,cnt1=0;
			Rep(j,0,n-1)if(dfn[j]>=dfn[i]&&dfn[j]<=ed[i])id[j]=cnt++,vis[j]=1;else id[j]=cnt1++,vis[j]=2;
			if(cnt!=f[dep-2])while(1);if(cnt1!=f[dep-1])while(1);
			Rep(j,0,n-1)for(auto k:G[j])if(vis[j]==vis[k]){
				if(vis[j]==1)p1[id[j]].pb(id[k]);else p2[id[j]].pb(id[k]);
			}return check(p1,dep-2)&&check(p2,dep-1);
		}
	}else if(cnt==2){
		int x=-1,y=-1;
		Rep(i,0,f[dep]-1)if(sz[i]==f[dep-2])(~x?y=i:x=i);
		vector<vector<int> >p1,p2,p3;p1.clear(),p2.clear(),p3.clear(),p1.resize(f[dep-2]),p2.resize(f[dep-2]),p3.resize(f[dep-3]);
		static int vis[MAXN],id[MAXN];int cnt=0,cnt1=0,cnt2=0;
		Rep(j,0,n-1)if(dfn[j]>=dfn[x]&&dfn[j]<=ed[x])id[j]=cnt++,vis[j]=1;else if(dfn[j]>=dfn[y]&&dfn[j]<=ed[y])id[j]=cnt1++,vis[j]=2;else id[j]=cnt2++,vis[j]=3;
		if(cnt!=f[dep-2])while(1);if(cnt1!=f[dep-2])while(1);if(cnt2!=f[dep-3])while(1);
		Rep(j,0,n-1)for(auto k:G[j])if(vis[j]==vis[k]){
			if(vis[j]==1)p1[id[j]].pb(id[k]);
			else if(vis[j]==2)p2[id[j]].pb(id[k]);
			else if(vis[j]==3)p3[id[j]].pb(id[k]);
		}return check(p1,dep-2)&&check(p2,dep-2)&&check(p3,dep-3);
	}else return 0;
}
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),f[0]=f[1]=1,tot=1;
	for(int i=2;f[i-1]+f[i-2]<=n;i++)f[++tot]=f[i-1]+f[i-2];
	Rep(i,1,tot)p[f[i]]=i;G.resize(n);
	Rep(i,1,n-1){int x=read()-1,y=read()-1;G[x].pb(y),G[y].pb(x);}
	if(!p[n])puts("NO");else puts(check(G,p[n])?"YES":"NO");
	return 0;
}