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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define sqr 500
//#define mp make_pair
#define mid (l+r)/2
#define le node * 2
#define ri node * 2 + 1
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef short int si;
typedef double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef pair<double,ll>pdi;
const ll inf=1e18;
const ll mod=1e9+7;
const ld Pi=acos(-1);
int n ;
vpi v [200009] ;
int done [200009] , fib [200009] ;
map < int , int > ok ;
//
vi nodes ;
int sz [200009] , idedge [200009] , P [200009] ;
void build ( int node , int p ) {
    sz [node] = 1 ;
    nodes .pb ( node ) ;
    if ( node == p ) idedge [node] = -1 , P [node] = -1 ;
    for ( int i = 0 ; i < v [node] .size () ; i ++ ) {
        int u = v [node][i] .fi , x = v [node][i] .se ;
        if ( u != p && ! done [x] ) {
            build ( u , node ) ;
            sz [node] += sz [u] ;
            P [u] = node ;
            idedge [u] = x ;
        }
    }
}

int f ( int St ) {
    nodes.clear () ;
    build ( St , St ) ;
    if ( sz [St] == 1 ) return 1 ;
    if ( !ok [sz[St]] ) return 0 ;

    int ret = 0 ;
    for ( int i = 0 ; i < nodes .size () ; i ++ ) {
        int node = nodes [i] ;
        if ( idedge [node] == -1 || P [node] == -1 ) C ;

        if ( sz [node] > 0 && ok [sz [node]] && sz [St] - sz [node] >0 && ok [sz[St]-sz[node]] ) {
            done [idedge[node]] = 1 ;
            return min ( f ( node ) , f ( P[node] ) ) ;
        }
    }
    return 0 ;
}
int main () {
    cin >> n ;
    for ( int i = 0 ; i < n - 1 ; i ++ ) {
        int a , b ;
        cin >> a >> b ;
        a -- , b -- ;
        v [a] .pb ( { b , i } ) ;
        v [b] .pb ( { a , i } ) ;
    }
    int it = 2 ;
    fib [0] = fib [1] = 1 ;
    ok [1] = 1 ;
    while ( 1 ) {
        fib [it] = fib [it-1] + fib [it-2] ;
        ok [fib[it]] = 1 ;
        if ( fib [it] > n ) break ;
        it ++ ;
    }
    cout << ( f (0) ? "YES" : "NO" ) << endl ;
}