← 返回题目列表

AtCoder · arc152_f

F. 树上的吸引力

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

你有一棵树 N 顶点编号 1 to N。 的 i第一条边连接两个顶点 a_i 和 b_i (1\leq i\leq N-1).

最初,一块被放置在顶点 1。您将准确执行以下操作 N 次。

  • 选择当前没有被棋子占据且之前操作中从未选择过的顶点,并将棋子向所选顶点移动一个顶点。

执行操作的方法 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}

输出

将答案打印为整数。


示例输入 1

4
1 2
2 4
3 4

示例输出 1

3

如果选择顶点 3, 1, 2, 4 按照这个顺序,该块将沿着路径移动 1 → 2 → 1 → 2 → 4。这是一个理想的过程。


示例输入 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