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:
import java.util.*;
import java.io.*;

public class HelloWorld {

	static class FastScanner
{
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }

    public int nextInt() {
        return (int) nextLong();
    }

    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }

    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }

    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }

    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}

	static int N = 200005;
	static int pu = 0;
	static int pv = 0;
	static int kd = 0;
	static int n;
	static int[] siz;
	static ArrayList<Integer> fib;
	static ArrayList<Integer>[] G;

	static void NO() {
		System.out.println("NO");
		System.exit(0);
	}

	static void GetSize(int u, int fa) {
		siz[u] = 1;
		for(int e : G[u]) {
			int v = e;
			if(v == fa) continue;
			GetSize(v, u);
			siz[u] += siz[v];
		}
	}

	static void CutEdge(int u, int fa, int k) {
		for(int e : G[u]) {
			if(pu != 0) return;
			int v = e;
			if(v == fa) continue;
			if(siz[v] == fib.get(k-1) || siz[v] == fib.get(k-2)) {
				pu = u;
				pv = v;
				if(siz[v] == fib.get(k-1)) kd = k-1;
				else kd = k-2;
				break;
			}
			CutEdge(v, u, k);
		}
	}

	static void Check(int u, int k) {
		if(k <= 1) return;
		GetSize(u, 0);
		pu = 0; pv = 0; kd = 0;
		CutEdge(u, 0, k);
		if(pu == 0) NO();
		int index = -1;
		for(int i = 0; i < G[pu].size(); i++) if(G[pu].get(i) == pv) index = i;
		if(index != -1) G[pu].remove(index);
		index = -1;
		for(int i = 0; i < G[pv].size(); i++) if(G[pv].get(i) == pu) index = i;
		if(index != -1) G[pv].remove(index);
		final int temp1 = pu;
		final int temp2 = kd;
		final int temp3 = pv;
		Check(temp3, temp2);
		if(temp2 == k-2) Check(temp1, k-1);
		else Check(temp1, k-2);
	}

	public static void main(String[] args) throws Exception {
		FastScanner infile = new FastScanner();
		PrintWriter writer = new PrintWriter(System.out);
		siz = new int[N];
		fib = new ArrayList<Integer>();
		G = new ArrayList[N];
		for(int i = 0; i < N; i++) G[i] = new ArrayList<Integer>();
		n = infile.nextInt();
		fib.add(1);
		fib.add(1);
		for(int i = 1; ; i++) {
			if(fib.get(i) >= n) break;
			int new_fib = fib.get(i) + fib.get(i-1);
			fib.add(new_fib);
		}
		StringTokenizer st;
		for(int i = 1; i < n; i++) {
			int u, v;
			u = infile.nextInt();
			v = infile.nextInt();
			G[u].add(v);
			G[v].add(u);
		}
		if(fib.get(fib.size()-1) != n) NO();
		Check(1, fib.size()-1);
		writer.println("YES");
		writer.close();
 	}
}