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

public class Main {

    static TreeSet<Integer> valid;
    static ArrayList<Integer> adjList[];
    static int[] size, parent;
    static int tmp;
    static boolean[] rem;


    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner();
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt();
        fillValid(n);
        adjList = new ArrayList[n];
        for (int i = 0; i < n; i++)
            adjList[i] = new ArrayList<>();
        size = new int[n];
        parent = new int[n];
        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
            adjList[u].add(v);
            adjList[v].add(u);
        }
        predfs(0, 0);
        rem = new boolean[n];
        out.println(check(0, 0) ? "YES" : "NO");
        out.flush();
        out.close();
    }

    static boolean check(int u, int p) {
        if (!valid.contains(size[u])) return false;
        if (size[u] <= 2) return true;
        int a = valid.lower(size[u]), b = (a == 1 ? 1 : valid.lower(a));
        tmp = -1;
        checkHelper(u, p, a, b);
        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]) && check(u, p);
    }

    static void checkHelper(int u, int p, int a, int b) {
        if (tmp != -1) return;
        for (int v : adjList[u]) {
            if (rem[v] || v == p) continue;
            if (size[v] == a || size[v] == b) {
                tmp = v;
                return;
            }
            checkHelper(v, u, a, b);
        }
    }


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


    static void predfs(int u, int p) {
        size[u] = 1;
        parent[u] = p;
        for (int v : adjList[u])
            if (v != p) {
                predfs(v, u);
                size[u] += size[v];
            }
    }


    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

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

        public Scanner(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

        public int[] nextIntArray(int n) throws IOException {
            int[] ans = new int[n];
            for (int i = 0; i < n; i++)
                ans[i] = nextInt();
            return ans;
        }

        public long[] nextLongArray(int n) throws IOException {
            long[] ans = new long[n];
            for (int i = 0; i < n; i++)
                ans[i] = nextLong();
            return ans;
        }

        public Integer[] nextIntegerArray(int n) throws IOException {
            Integer[] ans = new Integer[n];
            for (int i = 0; i < n; i++)
                ans[i] = nextInt();
            return ans;
        }

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

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

        public String nextLine() throws IOException {
            return br.readLine();
        }

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

        public boolean ready() throws IOException {
            return br.ready();
        }


    }
}