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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.TreeSet;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Vector;
import java.util.Stack;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author sarthakmanna
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EFibTree solver = new EFibTree();
        solver.solve(1, in, out);
        out.close();
    }

    static class EFibTree {
        boolean[] fibo;
        int N;
        TreeSet<Integer>[] graph;
        int[] childCount;
        int[] parent;

        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int i, j, k;
            fibo = new boolean[200_005];
            int x = 1, y = 1;
            while (x <= 200_000) {
                fibo[x] = true;
                int z = x + y;
                x = y;
                y = z;
            }

            N = in.nextInt();
            graph = new TreeSet[N];
            for (i = 0; i < N; ++i) graph[i] = new TreeSet<>();
            for (i = 1; i < N; ++i) {
                int a = in.nextInt() - 1, b = in.nextInt() - 1;
                graph[a].add(b);
                graph[b].add(a);
            }

            childCount = new int[N];
            parent = new int[N];
            Arrays.fill(parent, -7);
            fillChildCount(0, -7);

            if (!fibo[childCount[0]]) {
                out.println("NO");
                return;
            }

            Stack<Integer> stack = new Stack<>();
            stack.add(0);
            while (!stack.isEmpty()) {
                int top = stack.pop();
                if (!fibo[childCount[top]]) {
                    out.println("NO");
                    return;
                } else if (childCount[top] <= 3) {
                    continue;
                }
                int[] breakpoint = findBreakpoint(top, -7, childCount[top]);
                if (breakpoint == null) {
                    out.println("NO");
                    return;
                }
                int u = breakpoint[0], v = breakpoint[1];
                graph[u].remove(v);
                graph[v].remove(u);
                parent[v] = -7;
                subtractFromAncestors(u, childCount[v]);
                stack.add(top);
                stack.add(v);
            }
            out.println("YES");
        }

        void fillChildCount(int node, int par) {
            childCount[node] = 1;
            parent[node] = par;
            for (int itr : graph[node])
                if (itr != par) {
                    fillChildCount(itr, node);
                    childCount[node] += childCount[itr];
                }
        }

        int[] findBreakpoint(int node, int par, int sz) {
            for (int itr : graph[node])
                if (itr != par) {
                    if (fibo[childCount[itr]] && fibo[sz - childCount[itr]]) {
                        return new int[]{node, itr};
                    }
                    int[] tmp = findBreakpoint(itr, node, sz);
                    if (tmp != null) return tmp;
                }
            return null;
        }

        void subtractFromAncestors(int node, int val) {
            while (node >= 0) {
                childCount[node] -= val;
                node = parent[node];
            }
        }

    }

    static class FastReader {
        static final int BUFSIZE = 1 << 20;
        static byte[] buf;
        static int index;
        static int total;
        static InputStream in;

        public FastReader(InputStream is) {
            try {
                in = is;
                buf = new byte[BUFSIZE];
            } catch (Exception e) {
            }
        }

        private int scan() {
            try {
                if (index >= total) {
                    index = 0;
                    total = in.read(buf);
                    if (total <= 0)
                        return -1;
                }
                return buf[index++];
            } catch (Exception | Error e) {
                System.err.println(e.getMessage());
                return 13 / 0;
            }
        }

        public int nextInt() {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+')
                c = scan();
            for (; c >= '0' && c <= '9'; c = scan())
                val = (val << 3) + (val << 1) + (c & 15);
            return neg ? -val : val;
        }

    }
}