E - Fibonacci Subtree

問題

yama_can くんは、新しい根付き木（ここでは、グラフ理論の木）の種類を思いつき、それをフィボナッチ木として命名しました。

• レベル $0$ のフィボナッチ木は1つの頂点から構成される木である
• レベル $1$ のフィボナッチ木は1つの頂点から構成される木である
• レベル $i + 2$ のフィボナッチ木は新しく1つの根を作り、レベル $i$ のフィボナッチ木とレベル $i+1$ のフィボナッチ木の根をそれぞれ新しい根に辺を貼ってできる木である。

さて、yama_can くんは今自分が持っている木がフィボナッチ木の部分木であるかが気になりました。
木 が与えられるので、それがあるレベルのフィボナッチ木の部分木となる最小のレベルを出力してください。
フィボナッチ木の部分木となりえない場合は -1 を出力してください。

ただし、「木 $T$ の部分木」とは木 $T$ のある2つの頂点 $A, B$ を選択し、$A$ を始点とし $B$ を含むパスの終点となる頂点をすべて削除する操作を繰り返して得られる木です。

木は、入力で与えられる長さ $N-1$ の数列 $U_i, V_i$ についてを $U_i, V_i$ をつなぐ $N-1$ 個の辺からなる木として与えられます。

制約

• $1\leq N\leq 2\times 10^5$
• グラフは木である

入力

$N$

$U_1~V_1$

$U_2~V_2$

$\vdots$

$U_{N-2}~V_{N-2}$

$U_{N-1}~V_{N-1}$

小課題

• 小課題1 (200点)
  • $1\leq N\leq 5000$
• 小課題2 (325点)
  • 追加の制約はありません

入力例1

4
1 2
2 3
3 4
Copy

この入力はすべての小課題の制約を満たします。

出力例1

3
Copy

入力例2

2
2 1
Copy

出力例2

2
Copy

入力例3

3
1 2
1 3

Copy

出力例3

2

Copy