Vanya wants to minimize a tree. He can perform the following Operation multiple times: choose a vertex v, and two disjoint (except for v) paths of equal length a0?=?v, a1, ..., ak, and b0?=?v, b1, ..., bk. Additionally, vertices a1, ..., ak, b1, ..., bk must not have any neighbours in the tree other than adjacent vertices of corresponding paths. After that, one of the paths may be merged into the other, that is, the vertices b1, ..., bk can be effectively erased:

Help Vanya determine if it possible to make the tree into a path via a sequence of described operations, and if the answer is positive, also determine the shortest length of such path.

The first line of input contains the number of vertices n (2?≤?n?≤?2·105).

Next n?-?1 lines describe edges of the tree. Each of these lines contains two space-separated integers u and v (1?≤?u,?v?≤?n, u?≠?v) — indices of endpoints of the corresponding edge. It is guaranteed that the given graph is a tree.

If it is impossible to obtain a path, PRint -1. Otherwise, print the minimum number of edges in a possible path.

61 22 32 44 51 6output
3input
71 21 33 41 55 66 7output
-1Note
In the first sample case, a path of three edges is obtained after merging paths 2?-?1?-?6 and 2?-?4?-?5.
It is impossible to perform any operation in the second sample case. For example, it is impossible to merge paths 1?-?3?-?4 and 1?-?5?-?6, since vertex 6 additionally has a neighbour 7 that is not present in the corresponding path.
題意：
給一棵樹，如果兩條鏈，像上面一樣，a[i]和b[i]都沒有鄰居，就可以合并它們，問最后能不能合并成一條鏈，且要求鏈長度最小
題解：
從葉子節點bfs,對于每一個節點用set保存從他下方的節點到這個節點的鏈的長度，如果有相同長度的就會自動“合并”（set的功能）。邊bfs邊刪邊，不斷取葉子結點進行向上縮。
詳見代碼
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>#include<set>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=2e5+100;set<int> g[maxn];set<int> d[maxn];queue<int> q;int vis[maxn];int re(int x){    while(x%2==0)        x/=2;    return x;}int solve(){    while(!q.empty())    {        int u=q.front();        q.pop();        if(vis[u]) continue;        if(g[u].size()==1)        {            if(d[u].size()==1)            {                int v=*g[u].begin();                if(vis[v]) continue;                g[u].erase(v),g[v].erase(u);                d[v].insert(*d[u].begin()+1);                if(g[v].size()<=1)                q.push(v);                vis[u]=1;            }        }        else if(g[u].size()==0)        {            if(d[u].size()>=3) return -1;            else if(d[u].size()==2)                return re(*d[u].begin()+*d[u].rbegin());            else return re(*d[u].begin());        }    }    return -1;}int main(){    int n;    scanf("%d",&n);    rep(i,1,n)    {        int u,v;        scanf("%d%d",&u,&v);        g[u].insert(v),g[v].insert(u);    }    rep(i,1,n+1) if(g[i].size()==1) q.push(i),d[i].insert(0);    memset(vis,0,sizeof(vis));    printf("%d/n",solve());    return 0;}