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 mp make_pair
typedef long long ll;
 
typedef vector<vector<pair<int,pair<int,bool>>>> graph;
 
vector<int>FIB;
vector<int>rev;
int contador = 1;
int fillSizes(graph &adj, int node, int parent, int n){
	int total = 1;
	int saltadito = -1;
	for (int i = 0; i < adj[node].size(); i ++){
		if (!adj[node][i].second.second) continue;
		int node2 = adj[node][i].first;
		if (node2 == parent){
			saltadito = i;
			continue;
		}
		adj[node][i].second.first = fillSizes(adj, node2, node, n);
		total += adj[node][i].second.first;
	}
	if (saltadito != -1)
		adj[node][saltadito].second.first = n - total;
	return total;
}
 
bool isFib(graph &adj, int indx, int node){
	if (indx == 1 or indx == 0) return true;
 
	int aux = fillSizes(adj, node, -1, FIB[indx]);
 
	int bign = FIB[indx - 1];
	int smalln = FIB[indx - 2];
 
	queue<int> cola;
	cola.push(node);
	rev[node] = contador;
	vector<pair<int, int> >posibilidades;
	while(!cola.empty()){
		int node1 = cola.front();
		cola.pop();
		for (int i = 0; i < adj[node1].size(); i ++){
			if (!adj[node1][i].second.second) continue;
			int node2 = adj[node1][i].first;
			if (adj[node1][i].second.first == bign){
				posibilidades.push_back(mp(node1, i));
			}
			if (rev[node2] != contador){
				rev[node2] = contador;
				cola.push(node2);
			}
		}
	}
	contador ++;
	if (posibilidades.size() == 0) return false;
 
	for (auto &principal : posibilidades){
		adj[principal.first][principal.second].second.second = false;
		int node2 = adj[principal.first][principal.second].first;
		pair<int, int> del = mp(-1, -1);
		for (int i = 0; i < adj[node2].size(); i ++){
			if (adj[node2][i].first == principal.first){
				adj[node2][i].second.second = false;
				del = mp(node2, i);
				break;
			}
		}
		if (isFib(adj, indx - 1, node2) and isFib(adj, indx - 2, principal.first)) return true;
		adj[principal.first][principal.second].second.second = true;
		adj[del.first][del.second].second.second = true;
		return false;
	}
	return false;
}
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	FIB.resize(1e6, 0);
	FIB[0] = 1;
	FIB[1] = 1;
	for (int i = 2; i < FIB.size(); i ++){
		FIB[i] = FIB[i - 1] + FIB[i - 2];
	}
	int n;
	cin >> n;
	rev.resize(n, 0);
	graph adj(n);
	for (int i = 0; i < n - 1; i ++){
		int a, b;
		cin >> a >> b;
		a --; b --;
		adj[a].push_back(mp(b, mp(-1, true)));
		adj[b].push_back(mp(a, mp(-1, true)));
	}
 
	int indx = -1;
	for (int i = 0; i < FIB.size(); i ++){
		if (FIB[i] > 1e6) break;
		if (FIB[i] == n) {
			indx = i;
			break;
		}
	}
	if (indx == -1) {
		cout << "NO\n";
		return 0;
	}
	if (isFib(adj, indx, 0)) cout << "YES\n";
	else cout << "NO\n";
}