配点 : $1000$ 点

問題文

頂点に $1$ から $N$ までの番号がついた $N$ 頂点の木が与えられます。 この木の $i$ 番目の辺は、$2$ 頂点 $a_i,b_i$ を結んでいます $(1\leq i\leq N-1)$ 。

はじめ、頂点 $1$ に駒が置いてあり、あなたはこれから、以下の操作をちょうど $N$ 回行います。

• その時点で駒が置かれておらず、かつ今までの操作で一度も選択されていない頂点を $1$ つ選び、 駒を選んだ頂点の方向に $1$ つ動かす。

$N$ 回の操作を終えた後、駒が頂点 $N$ に置いてあるような手順を「よい手順」と呼びます。 さらに、よい手順のうち、手順中に駒が置かれたことのある頂点数（頂点 $1,N$ を含む）が最小となるものを「最良の手順」と呼びます。

最良の手順において、手順中に駒が置かれたことのある頂点の個数を求めてください。 ただし、よい手順が存在しないときは -1 と答えてください。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i,b_i \leq N$
• 入力される値はすべて整数である
• 与えられるグラフは木である

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $b_1$

$a_2$ $b_2$

$\vdots$

$a_{N-1}$ $b_{N-1}$

出力

答えを整数で出力せよ。

4
1 2
2 4
3 4

3

頂点 $3,1,2,4$ の順で選択すると、駒の位置は開始時から順に $1$ → $2$ → $1$ → $2$ → $4$ となり、これが最良の手順の一例です。

6
1 6
2 6
2 3
3 4
4 5

-1

よい手順が存在しません。

14
1 2
1 3
3 4
3 5
5 6
6 7
5 8
8 9
8 14
14 10
10 11
14 12
12 13

5