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.io.PrintStream;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Stack;
import java.util.ArrayList;
import java.util.AbstractCollection;
import java.util.Vector;
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;
        myTreeSetInteger[] 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 myTreeSetInteger[N];
            for (i = 0; i < N; ++i) graph[i] = new myTreeSetInteger();
            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 NodeInt {
        NodeInt parent;
        NodeInt left;
        NodeInt right;
        int value;
        int size;
        int height;

        NodeInt(int v) {
            value = v;
            size = height = 1;
        }

        NodeInt finalisePosition(NodeInt root) {
            int lheight = findDepth(left), rheight = findDepth(right);

            if (lheight > rheight + 1) {
                if (findDepth(left.right) > findDepth(left.left))
                    root = left.rotateLeft(root);
                root = rotateRight(root);
            } else if (lheight + 1 < rheight) {
                if (findDepth(right.left) > findDepth(right.right))
                    root = right.rotateRight(root);
                root = rotateLeft(root);
            } else {
                setParameters();
            }

            return root;
        }

        NodeInt rotateRight(NodeInt root) {
            NodeInt A = this, B = left, P = parent;

            if (P != null) {
                if (P.left == this) P.left = B;
                else if (P.right == this) P.right = B;
                else System.exit(7 / 0);
            } else root = B;
            B.parent = A.parent;

            A.left = B.right;
            if (B.right != null) B.right.parent = A;
            B.right = A;
            A.parent = B;

            A.setParameters();
            B.setParameters();

            return root;
        }

        NodeInt rotateLeft(NodeInt root) {
            NodeInt A = this, B = right, P = parent;

            if (P != null) {
                if (P.left == this) P.left = B;
                else if (P.right == this) P.right = B;
                else System.exit(7 / 0);
            } else root = B;
            B.parent = A.parent;

            A.right = B.left;
            if (B.left != null) B.left.parent = A;
            B.left = A;
            A.parent = B;

            A.setParameters();
            B.setParameters();

            return root;
        }

        void setParameters() {
            size = 1 + findSize(left) + findSize(right);
            height = 1 + Math.max(findDepth(left), findDepth(right));
        }

        int size() {
            return size;
        }

        static int findDepth(NodeInt node) {
            return node == null ? 0 : node.height;
        }

        static int findSize(NodeInt node) {
            return node == null ? 0 : node.size();
        }

        public int compareTo(NodeInt node) {
            return Integer.compare(value, node.value);
        }

        public String toString() {
            return value + "";
        }

    }

    static class myTreeSetInteger implements Iterable<Integer> {
        NodeInt root;
        boolean allowDuplicates;
        private int itrInd;
        private ArrayList<NodeInt> dfsTrav = new ArrayList<>();

        public myTreeSetInteger() {
            root = null;
        }

        public myTreeSetInteger(boolean allowDupli) {
            root = null;
            allowDuplicates = allowDupli;
        }

        public boolean add(int value) {
            return add(new NodeInt(value));
        }

        public boolean remove(int value) {
            NodeInt actual = new NodeInt(value), toRemove = floor(actual);
            if (toRemove.compareTo(actual) != 0) return false;
            return remove(toRemove);
        }

        public int size() {
            return root == null ? 0 : root.size();
        }

        private boolean add(NodeInt toAdd) {
            if (root == null) {
                root = toAdd;
                return true;
            }

            NodeInt tr = root;
            while (true) {
                if (toAdd.compareTo(tr) < 0) {
                    if (tr.left == null) {
                        tr.left = toAdd;
                        toAdd.parent = tr;
                        break;
                    } else tr = tr.left;
                } else if (allowDuplicates || toAdd.compareTo(tr) > 0) {
                    if (tr.right == null) {
                        tr.right = toAdd;
                        toAdd.parent = tr;
                        break;
                    } else tr = tr.right;
                } else return false;
            }

            while (toAdd != null) {
                root = toAdd.finalisePosition(root);
                toAdd = toAdd.parent;
            }
            return true;
        }

        private boolean remove(NodeInt node) {
            if (root.size() == 1) {
                root = null;
                return true;
            }
            NodeInt p;

            if (node.left != null) {
                p = prev(node);
                if (p.parent != null) {
                    if (p.parent.left == p) p.parent.left = p.left;
                    else if (p.parent.right == p) p.parent.right = p.left;
                    else System.exit(7 / 0);
                }
                if (p.left != null) p.left.parent = p.parent;
            } else if (node.right != null) {
                p = next(node);
                if (p.parent != null) {
                    if (p.parent.left == p) p.parent.left = p.right;
                    else if (p.parent.right == p) p.parent.right = p.right;
                    else System.exit(7 / 0);
                }
                if (p.right != null) p.right.parent = p.parent;
            } else {
                if (node.parent.left == node) node.parent.left = null;
                else if (node.parent.right == node) node.parent.right = null;
                else System.exit(7 / 0);

                NodeInt tr = node.parent;
                while (tr != null) {
                    root = tr.finalisePosition(root);
                    tr = tr.parent;
                }
                return true;
            }


            NodeInt tr = p.parent;
            while (tr != node) {
                root = tr.finalisePosition(root);
                tr = tr.parent;
            }

            p.parent = node.parent;
            node.parent = null;
            p.left = node.left;
            node.left = null;
            p.right = node.right;
            node.right = null;

            if (p.parent != null) {
                if (p.parent.left == node) p.parent.left = p;
                else if (p.parent.right == node) p.parent.right = p;
                else System.exit(7 / 0);
            }
            if (p.left != null) p.left.parent = p;
            if (p.right != null) p.right.parent = p;

            if (root == node) root = p;
            while (p != null) {
                root = p.finalisePosition(root);
                p = p.parent;
            }

            return true;
        }

        private NodeInt floor(NodeInt node) {
            if (root == null) return null;

            NodeInt tr = root;
            while (true) {
                if (node.compareTo(tr) < 0) {
                    if (tr.left == null) return prev(tr);
                    else tr = tr.left;
                } else if (node.compareTo(tr) > 0) {
                    if (tr.right == null) return tr;
                    else tr = tr.right;
                } else return tr;
            }
        }

        private NodeInt prev(NodeInt node) {
            NodeInt parent;

            if (node.left != null) {
                node = node.left;
                while (node.right != null) node = node.right;
                return node;
            }

            while (true) {
                parent = node.parent;
                if (parent == null) return null;
                else if (parent.right == node) return parent;
                else node = parent;
            }
        }

        private NodeInt next(NodeInt node) {
            NodeInt parent;

            if (node.right != null) {
                node = node.right;
                while (node.left != null) node = node.left;
                return node;
            }

            while (true) {
                parent = node.parent;
                if (parent == null) return null;
                else if (parent.left == node) return parent;
                else node = parent;
            }
        }

        public Iterator<Integer> iterator() {
            dfsTrav.clear();
            dfs(root);
            itrInd = 0;
            Iterator<Integer> iterator = new Iterator<Integer>() {

                public boolean hasNext() {
                    return itrInd < size();
                }


                public Integer next() {
                    return dfsTrav.get(itrInd++).value;
                }
            };
            return iterator;
        }

        private void dfs(NodeInt node) {
            if (node == null) return;
            dfs(node.left);
            dfsTrav.add(node);
            dfs(node.right);
        }

        public String toString() {
            dfsTrav.clear();
            dfs(root);
            if (dfsTrav.isEmpty()) return "[]";
            else return dfsTrav.toString();
        }

    }

    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;
        }

    }
}