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.*;
 
import java.math.*;
import java.awt.Point;
 
public class CFTemplate {
    static final long MOD = 1000000007L;
    //static final long MOD2 = 1000000009L;
    //static final long MOD = 998244353L;
    //static final long INF = 500000000000L;
    static final int INF = 1100000000;
    static final int NINF = -100000;
    static FastScanner sc;
    static PrintWriter pw;
    static final int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};

    static ArrayList<Integer>[] tree;
    static int[] size;
    static int[] parent;

    static final int[] fib = {1, 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) {
        sc = new FastScanner();
        pw = new PrintWriter(System.out);

        int N = sc.ni();
        tree = new ArrayList[N];
        for (int i = 0; i < N; i++) tree[i] = new ArrayList<Integer>();

        for (int i = 0; i < N-1; i++) {
            int u = sc.ni()-1;
            int v = sc.ni()-1;
            tree[u].add(v);
            tree[v].add(u);
        }
        size = new int[N];
        parent = new int[N];
        subtreeDFS(0,-1);

        int X = -1;
        for (int i = 0; i < fib.length; i++) {
            if (size[0] == fib[i]) {
                X = i;
            }
        }

        if (X==-1) {
            pw.println("NO");
            pw.close();
            return;
        }

        boolean ans = divconq(0,X);
        if (ans)
            pw.println("YES");
        else
            pw.println("NO");
        pw.close();
    }

    public static boolean divconq(int n, int x) {
        if (x <= 1) return true;

        int cut = findCut(n,x-2);
        int cutx = x-2;
        int nx = x-1;

        if (cut==-1) {
            cut = findCut(n,x-1);
            cutx = x-1;
            nx = x-2;
        }
        if (cut==-1) return false;
        int p = parent[cut];

        //cut
        parent[cut] = -1;
        tree[cut].remove(Integer.valueOf(p));
        tree[p].remove(Integer.valueOf(cut));
        while (p >= 0) {
            size[p] -= size[cut];
            p = parent[p];
        }
        

        return divconq(cut,cutx) && divconq(n,nx);
    }

    public static int findCut(int n, int x) {
        if (size[n]==fib[x]) return n;

        for (int next: tree[n]) {
            if (next==parent[n]) continue;

            int v = findCut(next,x);
            if (v >= 0) return v;
        }
        return -1;
    }

    public static int subtreeDFS(int n, int p) {
        parent[n] = p;
        int sz = 1;
        for (int next: tree[n]) {
            if (next==p) continue;
            sz += subtreeDFS(next,n);
        }
        size[n] = sz;
        return sz;
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in), 32768);
            st = null;
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int ni() {
            return Integer.parseInt(next());
        }
 
        int[] intArray(int N, int mod) {
            int[] ret = new int[N];
            for (int i = 0; i < N; i++)
                ret[i] = ni()+mod;
            return ret;
        }
 
        long nl() {
            return Long.parseLong(next());
        }
 
        long[] longArray(int N, long mod) {
            long[] ret = new long[N];
            for (int i = 0; i < N; i++)
                ret[i] = nl()+mod;
            return ret;
        }
 
        double nd() {
            return Double.parseDouble(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}