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 JAVA):

Solution:
// practice with kaiboy
import java.io.*;
import java.util.*;

public class CF1491E extends PrintWriter {
	CF1491E() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1491E o = new CF1491E(); o.main(); o.flush();
	}

	int[] eo; int[][] ej;
	void append(int i, int j) {
		int o = eo[i]++;
		if (o >= 2 && (o & o - 1) == 0)
			ej[i] = Arrays.copyOf(ej[i], o << 1);
		ej[i][o] = j;
	}
	void remove(int i, int j) {
		int o = 0;
		while (ej[i][o] != j)
			o++;
		while (o + 1 < eo[i]) {
			ej[i][o] = ej[i][o + 1];
			o++;
		}
		eo[i]--;
	}
	int[] ff = new int[100];
	int u_, v_, f1, f2;
	int dfs(int p, int i) {
		int cnt = 1;
		for (int o = eo[i]; o-- > 0; ) {
			int j = ej[i][o];
			if (j != p)
				cnt += dfs(i, j);
		}
		if (cnt == f1) {
			u_ = i; v_ = p;
		} else if (cnt == f2) {
			u_ = p; v_ = i;
		}
		return cnt;
	}
	boolean check(int i, int k) {
		if (k <= 3)
			return true;
		u_ = -1; f1 = ff[k - 1]; f2 = ff[k - 2];
		dfs(-1, i);
		if (u_ == -1)
			return false;
		int u = u_, v = v_;
		remove(u, v);
		remove(v, u);
		return check(v, k - 2) && check(u, k - 1);
	}
	void main() {
		int n = sc.nextInt();
		if (n == 1) {
			println("YES");
			return;
		}
		ff[0] = ff[1] = 1;
		int k = 2;
		while ((ff[k] = ff[k - 1] + ff[k - 2]) < n)
			k++;
		if (ff[k] > n) {
			println("NO");
			return;
		}
		eo = new int[n]; ej = new int[n][2];
		for (int h = 0; h < n - 1; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			append(i, j);
			append(j, i);
		}
		println(check(0, k) ? "YES" : "NO");
	}
}