分数: 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