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.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

@SuppressWarnings("ConstantConditions")
public final class E {

    static TreeSet<Integer> fib;
    static int tmp;
    static boolean[] rem;

    public static void main(String[] args) throws IOException {
        final FastScanner sc = new FastScanner();
        final int n = sc.nextInt();
        final List<List<Integer>> g = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        final int[] size = new int[n];
        final int[] parent = new int[n];
        for (int i = 0; i < n - 1; i++) {
            final int u = sc.nextInt() - 1;
            final int v = sc.nextInt() - 1;
            g.get(u).add(v);
            g.get(v).add(u);
        }
        fillFib(n);
        dfs(0, -1, g, size, parent);
        rem = new boolean[n];
        System.out.println(check(0, -1, g, size, parent) ? "YES" : "NO");
    }

    private static void dfs(int u, int p, List<List<Integer>> g, int[] size, int[] parent) {
        size[u] = 1;
        parent[u] = p;
        for (int v : g.get(u)) {
            if (v != p) {
                dfs(v, u, g, size, parent);
                size[u] += size[v];
            }
        }
    }

    private static boolean check(int u, int p, List<List<Integer>> g, int[] size, int[] parent) {
        if (!fib.contains(size[u])) { return false; }
        if (size[u] <= 2) { return true; }
        final int a = fib.lower(size[u]);
        final int b = a == 1 ? 1 : fib.lower(a);
        tmp = -1;
        checkHelper(u, p, a, b, g, size);
        if (tmp == -1) { return false; }
        int par = parent[tmp];
        size[par] -= size[tmp];
        while (par != u) {
            par = parent[par];
            size[par] -= size[tmp];
        }
        rem[tmp] = true;
        return check(tmp, parent[tmp], g, size, parent) && check(u, p, g, size, parent);
    }

    private static void checkHelper(int u, int p, int a, int b, List<List<Integer>> g, int[] size) {
        if (tmp != -1) {
            return;
        }
        for (int v : g.get(u)) {
            if (rem[v] || v == p) {
                continue;
            }
            if (size[v] == a || size[v] == b) {
                tmp = v;
                return;
            }
            checkHelper(v, u, a, b, g, size);
        }
    }

    private static void fillFib(int n) {
        fib = new TreeSet<>();
        int a = 1, b = 1;
        fib.add(1);
        while (true) {
            final long cc = a + b;
            if (cc > n) {
                return;
            }
            final int c = a + b;
            fib.add(c);
            a = b;
            b = c;
        }
    }

    static final class Utils {
        private static class Shuffler {
            private static void shuffle(int[] x) {
                final Random r = new Random();

                for (int i = 0; i <= x.length - 2; i++) {
                    final int j = i + r.nextInt(x.length - i);
                    swap(x, i, j);
                }
            }

            private static void shuffle(long[] x) {
                final Random r = new Random();

                for (int i = 0; i <= x.length - 2; i++) {
                    final int j = i + r.nextInt(x.length - i);
                    swap(x, i, j);
                }
            }

            private static void swap(int[] x, int i, int j) {
                final int t = x[i];
                x[i] = x[j];
                x[j] = t;
            }

            private static void swap(long[] x, int i, int j) {
                final long t = x[i];
                x[i] = x[j];
                x[j] = t;
            }
        }

        public static void shuffleSort(int[] arr) {
            Shuffler.shuffle(arr);
            Arrays.sort(arr);
        }

        public static void shuffleSort(long[] arr) {
            Shuffler.shuffle(arr);
            Arrays.sort(arr);
        }

        private Utils() {}
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        private String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    //noinspection CallToPrintStackTrace
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        int[] nextIntArray(int n) {
            final int[] a = new int[n];
            for (int i = 0; i < n; i++) { a[i] = nextInt(); }
            return a;
        }

        long[] nextLongArray(int n) {
            final long[] a = new long[n];
            for (int i = 0; i < n; i++) { a[i] = nextLong(); }
            return a;
        }
    }
}