题目描述

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

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

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

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

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

输入格式

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

$N$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_{N-1}$ $b_{N-1}$

输出格式

答えを整数で出力せよ。

题目大意

你有一棵有 $N$ 个点的树。一开始，树上的 1 号节点处有一个卡片。

你需要进行以下操作恰好 $N$ 次：

• 选择一个之前没有被选择过的点，将卡片向那个点移动一条边。不能选择恰好在卡片位置的点

称一个选择点的顺序是 good 的，当且仅当 $N$ 次操作后卡片在 $N$ 号节点。

你需要回答，一个 good 的顺序在过程中卡片最少访问了多少个节点。或者报告不存在 good 的顺序。

4
1 2
2 4
3 4

3

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

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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