Contest Duration: - (local time) (120 minutes) Back to Home
F - Attraction on Tree /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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

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

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

### 制約

• 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}


### 入力例 1

4
1 2
2 4
3 4


### 出力例 1

3


### 入力例 2

6
1 6
2 6
2 3
3 4
4 5


### 出力例 2

-1


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

### 入力例 3

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


### 出力例 3

5


Score : 1000 points

### Problem Statement

You are given a tree with N vertices numbered 1 to N. The i-th edge connects two vertices a_i and b_i (1\leq i\leq N-1).

Initially, a piece is placed at vertex 1. You will perform the following operation exactly N times.

• Choose a vertex that is not occupied by the piece at that moment and is never chosen in the previous operations, and move the piece one vertex toward the chosen vertex.

A way to perform the operation N times is called a good procedure if the piece ends up at vertex N. Additionally, a good procedure is called an ideal procedure if the number of vertices visited by the piece at least once during the procedure (including vertices 1 and N) is the minimum possible.

Find the number of vertices visited by the piece at least once during an ideal procedure. If there is no good procedure, print -1 instead.

### Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq a_i,b_i \leq N
• All values in the input are integers.
• The given graph is a tree.

### Input

The input is given from Standard Input in the following format:

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


### Output

Print the answer as an integer.

### Sample Input 1

4
1 2
2 4
3 4


### Sample Output 1

3


If you choose vertices 3, 1, 2, 4 in this order, the piece will go along the path 12124. This is an ideal procedure.

### Sample Input 2

6
1 6
2 6
2 3
3 4
4 5


### Sample Output 2

-1


There is no good procedure.

### Sample Input 3

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


### Sample Output 3

5