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 fi first
#define se second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define _ << " "
#define ins(a, n, x) (a).insert((a).begin(), (n), (x));
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define __ << "\n"
#define vt vector

typedef long long int ll;
typedef double lf;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vl;

const int mod = 1e9 + 7;

inline int add(int a, int b) {a += b; if(a >= mod) a-= mod; if(a < 0) a += mod; return a;}
inline int mult(int a, int b) {return (long long) a * b % mod;}
inline int pot(int a, int b) {int ret = 1; while(b){if(b & 1) ret = mult(ret, a); a = mult(a, a); b >>= 1;} return ret;}
inline int divide(int a, int b) {return mult(a, pot(b, mod - 2));}
inline ll raand() {return (ll)rand() * RAND_MAX + rand();}
inline ll raaand() {return raand() * (mod - 7) + raand();}

void no() {
	cout << "NO\n";
	exit(0);
}

void yes() {
	cout << "YES\n";
	exit(0);
}

vt <vt <int> > g;
vt <int> col;

pii sol;
int par;
int ser1, ser2, cur_col, new_col = 0;

int rek(int node) {
	col[node] = new_col;
	int ret = 1;
	for(auto nei : g[node]) {
		if(col[nei] != cur_col) continue;
		int his = rek(nei);
		ret += his;
		if(his == ser1 || his == ser2) {
			sol = mp(his, nei);
			par = node;
		}
	}
	return ret;
}

void paint(int node, int dont) {
	col[node] = new_col;
	for (auto nei : g[node]) {
		if(nei == dont) continue;
		if(col[nei] != cur_col) continue;
		paint(nei, node);
	}
	return;
}

int main()
{
	srand(time(NULL));
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	g.insert(g.begin(), n, vt<int>());
	col.insert(col.begin(), n, -1);
	int u, v;
	REP(i, n - 1) {
		cin >> u >> v;
		u--; v--;
		g[u].pb(v);
		g[v].pb(u);
	}
	if(n < 3) yes();
	vt <int> fib;
	fib.pb(1);
	fib.pb(1);
	while(fib.back() < n) fib.pb(fib.back() + fib[(int)fib.size() - 2]);
	if(fib.back() != n) no();
	queue <pii> q;
	q.push(mp(0, (int)fib.size() - 1));
	while(!q.empty()) {
		int cur = q.front().first, cur_ptr = q.front().second;
		cur_col = col[cur];
		q.pop();
		if(fib[cur_ptr] == 1) continue;
		ser1 = fib[cur_ptr - 1];
		ser2 = fib[cur_ptr - 2];
		sol = mp(-1, -1);
		rek(cur);
		if(sol.first == -1) no();
		cur_col = new_col;
		new_col++;
		paint(sol.second, par);
		new_col++;
		if(sol.first == ser1) {
			q.push(mp(par, cur_ptr - 2));
			q.push(mp(sol.second, cur_ptr - 1));
		}
		else {
			q.push(mp(par, cur_ptr - 1));
			q.push(mp(sol.second, cur_ptr - 2));
		}
	}
	yes();
	return 0;
}