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:
// Don't place your source in a package
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;








// Please name your class Main
public class Main {

    static class FastScanner {//scanner from SecondThread
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

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

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(System.out);
        FastScanner fs=new FastScanner();
        int T=1;
        for(int t=0;t<T;t++){
            int n= fs.Int();
            List<int[]>g[]=new ArrayList[n];
            for(int i=0;i<g.length;i++){
                g[i]=new ArrayList<>();
            }

            for(int i=0;i<n-1;i++){
                int u=fs.Int()-1;int v=fs.Int()-1;
                g[u].add(new int[]{v,1});
                g[v].add(new int[]{u,1});
            }


            Solution sol=new Solution();
            sol.solution(out,g);
        }
        out.flush();

    }

}



class Solution{
    List<int[]>g[];
    int count[];
    int dp[];
    int cnt=0;
    int n;
    boolean res=false;
    int pos=-1;
    int posparent=-1;
    public void solution(PrintWriter out,List<int[]>g[]){
        //two ways to cur => we can cut any
        this.g=g;
        n=g.length;

        init(n);
        getCount(-1,0,-1,100000000);

        int fib=fib(n);
        if(fib==-1){
            out.println("NO");
            return;
        }


        dfs(-1,0,fib);
        out.println(res?"YES":"NO");
    }

    public void dfs(int parent,int root,int fib){
        if(res)return;



        if(dp[fib]<=3){
            cnt+=dp[fib];
            if(cnt==n){
                res=true;
            }
            return;
        }



        for(int p[]:g[root]){
            int next=p[0],state=p[1];
            if(state==0)continue;
            if(next!=parent){
                if(count[next]==dp[fib-1]||count[next]==dp[fib-2]){
                    pos=-1;
                    posparent=-1;
                    p[1]=0;
                    if(count[next]==dp[fib-1]){
                        getCount(-1,root,1,dp[fib-2]);
                        if(pos==-1){
                            System.out.println("NO");
                            System.exit(0);
                            return;
                        }

                        for(int x[]:g[next]){
                            if(x[0]==root)x[1]=0;
                        }
                        dfs(posparent,pos,fib-2);
                        dfs(-1,next,fib-1);

                    }
                    else if(count[next]==dp[fib-2]){
                        getCount(-1,root,1,dp[fib-1]);
                        if(pos==-1){
                            System.out.println("NO");
                            System.exit(0);
                            return;
                        }


                        for(int x[]:g[next]){
                            if(x[0]==root)x[1]=0;
                        }
                        dfs(posparent,pos,fib-1);
                        dfs(-1,next,fib-2);
                    }
                    return;
                }
                else{
                    dfs(root,next,fib);
                }
            }
        }

    }



    //get the subtree count
    public int getCount(int parent,int root,int dir,int cc){
        count[root]=1;
        for(int p[]:g[root]){
            int next=p[0],state=p[1];
            if(next!=parent&&state!=0){
                count[root]+=getCount(root,next,-1,cc);
            }
        }
        if(count[root]==cc){
            pos=root;
            posparent=parent;
        }
        return count[root];


    }

    public void init(int n){
        count=new int[n];
        dp=new int[31];
        dp[0]=dp[1]=1;
        for(int i=2;i<dp.length;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }

    }

    public int fib(int n){
        for(int i=0;i<dp.length;i++){
            if(dp[i]==n)return i;
        }
        return -1;
    }

    public void print(int A[]){
        for(int i:A){
            System.out.print(i+" ");
        }System.out.println();
    }


}

/*
8
1 6
1 2
2 3
3 4
4 5
6 7
7 8
* */