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 mp std::make_pair
#define pb push_back
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define ep emplace
#define eb emplace_back
 
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned int u32;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
 
const int max_N = 202401;
 
int n, nxt[2 * max_N], head[max_N], to[2 * max_N], size[max_N];
int fib[30], fib_id[max_N], tot;
bool vis[2 * max_N];
 
int read() {
	char c = gc(); int ans = 0; bool flag = true;
	while (!isdigit(c)) flag &= (c != '-'), c = gc();
	while (isdigit(c)) ans = 10 * ans + c - '0', c = gc();
	return flag ? ans : -ans;
}
void Write(int x) {
	if (x < 0) pc('-'), x = -x;
	if (x < 10) pc(x + '0');
	else Write(x / 10), pc(x % 10 + '0');
}
 
int min(int x, int y) {return x < y ? x : y;}
int max(int x, int y) {return x > y ? x : y;}
void _min(int &x, int y) {if (x > y) x = y;}
void _max(int &x, int y) {if (x < y) x = y;}
 
void add_edge(int u, int v) {
	nxt[++tot] = head[u], head[u] = tot, to[tot] = v;
}
 
void dfs(int x, int fa, int &tmp1, int &tmp2, int &X, int &Y) {
	size[x] = 1;
	for (int i = head[x]; i; i = nxt[i]) {
		if (to[i] == fa || vis[i]) continue;
		dfs(to[i], x, tmp1, tmp2, X, Y), size[x] += size[to[i]];
		if (size[to[i]] == X || size[to[i]] == Y)
			tmp1 = i, tmp2 = (i & 1 ? i + 1 : i - 1);
	}
}

void Assert(bool flag) {
	if (!flag) puts("NO"), exit(0);
}

void solve(int x, int y) {
	if (y <= 3) return;
	int tmp1 = 0, tmp2 = 0, X = fib[y - 2], Y = fib[y - 1];
	dfs(x, 0, tmp1, tmp2, X, Y); Assert(tmp1); vis[tmp1] = vis[tmp2] = true;
	if (size[to[tmp1]] == X) solve(to[tmp1], y - 2), solve(to[tmp2], y - 1);
	else solve(to[tmp1], y - 1), solve(to[tmp2], y - 2);
}

int main() {
	n = read();
	for (int i = 0, u = 0, v = 1; v <= n; )
		fib[fib_id[v] = ++i] = v, std::swap(u, v), v += u;
	for (int i = 1, u, v; i < n; i++)
		u = read(), v = read(), add_edge(u, v), add_edge(v, u);
	if (!fib_id[n]) return puts("NO"), 0;
	return solve(1, fib_id[n]), puts("YES"), 0;
}