题目描述

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接着顶点 $a_i$ 和 $b_i$（$1 \leq i \leq N-1$）。

一开始，棋子放在顶点 $1$ 上。接下来，你需要恰好进行 $N$ 次如下操作：

• 每次选择一个当前没有棋子且在之前的操作中从未被选择过的顶点，然后将棋子向着被选中的顶点的方向移动一步。

在 $N$ 次操作结束后，如果棋子恰好停在顶点 $N$，则称该操作序列为“好方案”。在所有好方案中，使得操作过程中棋子曾经停留过的顶点数（包括顶点 $1$ 和 $N$）最少的方案，称为“最优方案”。

请你求出在最优方案中，操作过程中棋子曾经停留过的顶点数。如果不存在好方案，请输出 $-1$。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

请输出一个整数，表示答案。

样例 1

输入

4
1 2
2 4
3 4

输出

3

样例 2

输入

6
1 6
2 6
2 3
3 4
4 5

输出

-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

输出

5

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq N$
• 输入的所有值均为整数
• 给定的图是一棵树

样例解释 1

按 $3,1,2,4$ 的顺序选择顶点，棋子的位置依次为 $1 \to 2 \to 1 \to 2 \to 4$，这是最优方案的一种。

样例解释 2

不存在好方案。

由 ChatGPT 4.1 翻译