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:
//stan hu tao
//join nct ridin by first year culture reps
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1491E
{
    static Edge[][] edges;
    public static void main(String hi[]) throws Exception
    {
        kth = new int[300000];
        Arrays.fill(kth, -1);
        kth[1] = 1;
        int temp0 = 1, temp1 = 1;
        int tag = 2;
        int[] map = new int[50];
        while(true)
        {
            int temp = temp0+temp1;
            if(temp > 200000)
                break;
            map[tag] = temp;
            kth[temp] = tag++;
            temp0 = temp1;
            temp1 = temp;
        }
        FastScanner infile = new FastScanner();
        int N = infile.nextInt();
        if(kth[N] == -1)
        {
            System.out.println("NO");
            return;
        }
        int[] freq = new int[N+1];
        int[] input = new int[2*N-2];
        for(int i=0; i < 2*N-2; i+=2)
        {
            int a = infile.nextInt();
            int b = infile.nextInt();
            input[i] = a;
            input[i+1] = b;
            freq[a]++;  freq[b]++;
        }
        edges = new Edge[N+1][];
        for(int v=1; v <= N; v++)
            edges[v] = new Edge[freq[v]];
        int edgeid = 0;
        for(int i=0; i < 2*N-2; i+=2)
        {
            int a = input[i];
            int b = input[i+1];
            edges[a][--freq[a]] = new Edge(b, edgeid);
            edges[b][--freq[b]] = new Edge(a, edgeid);
            edgeid++;
        }
        cut = new boolean[N];
        String res = "yES";
        ArrayDeque<Integer> qq = new ArrayDeque<Integer>();
        qq.add(1);  qq.add(N);
        sizes = new int[N+1];
        while(qq.size() > 0)
        {
            int root = qq.poll();
            int currval = qq.poll();
            if(currval <= 3)
                continue;
            dfs1(root, -1);
            ArrayDeque<Integer> q = new ArrayDeque<Integer>();
            q.add(root);    q.add(-1);
            int a = map[kth[currval]-1];
            int b = map[kth[currval]-2];
            boolean found = false;
            bfs:while(q.size() > 0)
            {
                int curr = q.poll();
                int par = q.poll();
                for(Edge e: edges[curr])
                    if(e.to != par && !cut[e.id])
                    {
                        if(sizes[e.to] == a)
                        {
                            qq.add(e.to);
                            qq.add(a);
                            qq.add(curr);
                            qq.add(b);
                            cut[e.id] = found = true;
                            break bfs;
                        }
                        else if(sizes[e.to] == b)
                        {
                            qq.add(e.to);
                            qq.add(b);
                            qq.add(curr);
                            qq.add(a);
                            cut[e.id] = found = true;
                            break bfs;
                        }
                        q.add(e.to);
                        q.add(curr);
                    }
            }
            if(!found)
            {
                res = "nO";
                break;
            }
        }
        System.out.println(res);
    }
    static int[] kth;
    static boolean[] cut;
    static int[] sizes;
    public static void dfs1(int curr, int par)
    {
        sizes[curr] = 1;
        for(Edge e: edges[curr])
            if(e.to != par && !cut[e.id])
            {
                dfs1(e.to, curr);
                sizes[curr] += sizes[e.to];
            }
    }
}
class Edge
{
    public int to;
    public int id;

    public Edge(int a, int b)
    {
        to = a;
        id = b;
    }
}
class FastScanner
{
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }

    public int nextInt() {
        return (int) nextLong();
    }

    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }

    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }

    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }

    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}