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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class SolutionE extends Thread {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                                            InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    private static final FastReader scanner = new FastReader();
    private static final PrintWriter out = new PrintWriter(System.out);

    static int[] fibonacciNumbers = {1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418};

    public static void main(String[] args) {
        solve();
        out.close();
    }

    static class Edge {
        Node a;
        Node b;

        boolean isDeleted = false;
        int amountOnA = 0;
        int amountOnB = 0;

        public Edge(Node a, Node b) {
            this.a = a;
            this.b = b;
        }

        public void removeEdge() {
            isDeleted = true;
        }
    }

    static Edge edgeCut = null;

    static class Node {
        //standard attributes
        int index;
        List<Edge> neighbors;

        public Node(int index) {
            this.index = index;
            this.neighbors = new ArrayList<>();
        }

        int dfs1(int fibIndex, int fromIndex) {
            int amountAfter = 1;

            for (Edge edge : neighbors) {
                Node neighbor;
                boolean thisIsA;
                if (edge.a.index == this.index) {
                    neighbor = edge.b;
                    thisIsA = true;
                } else {
                    neighbor = edge.a;
                    thisIsA = false;
                }

                if (edge.isDeleted || neighbor.index == fromIndex) {
                    continue;
                }

                int successors = neighbor.dfs1(fibIndex, this.index);
                if (successors < 0) {
                    return -1;
                }

                amountAfter += successors;
                if (thisIsA) {
                    edge.amountOnB = successors;
                    edge.amountOnA = fibonacciNumbers[fibIndex] - successors;
                } else {
                    edge.amountOnA = successors;
                    edge.amountOnB = fibonacciNumbers[fibIndex] - successors;
                }

                if (successors == fibonacciNumbers[fibIndex-1] || successors == fibonacciNumbers[fibIndex-2]) {
                    edgeCut = edge;
                    return -1;
                }
            }
            return amountAfter;
        }
    }

    private static void solve() {
        int n = scanner.nextInt();
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(i);
        }
        for (int i = 0; i < n-1; i++) {
            int ui = scanner.nextInt();
            int vi = scanner.nextInt();
            Edge edge = new Edge(nodes[ui-1], nodes[vi-1]);
            nodes[ui-1].neighbors.add(edge);
            nodes[vi-1].neighbors.add(edge);
        }

        if (isFibonacciNumber(n) < 0) {
            out.println("NO");
            return;
        }

        //preCalc
        if (isFibTree(nodes[0], isFibonacciNumber(n))) {
            out.println("YES");
        } else {
            out.println("NO");
        }
    }

    static boolean isFibTree(Node root, int treeSizeAsFibIndex) {
        if (treeSizeAsFibIndex <= 2) {
            return true;
        }

        edgeCut = null;
        root.dfs1(treeSizeAsFibIndex, -1);

        if (edgeCut == null) {
            return false;
        }

        edgeCut.removeEdge();

        Edge save = edgeCut;
        if (fibonacciNumbers[treeSizeAsFibIndex-1] == edgeCut.amountOnB) {
            return isFibTree(save.a, treeSizeAsFibIndex-2) &&
                   isFibTree(save.b, treeSizeAsFibIndex-1);
        } else {
            return isFibTree(save.a, treeSizeAsFibIndex-1) &&
                   isFibTree(save.b, treeSizeAsFibIndex-2);
        }
    }

    static int isFibonacciNumber(int n) {
        return Arrays.binarySearch(fibonacciNumbers, n);
    }
}