Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
頂点に 1 から N までの番号がついた N 頂点の木が与えられます。 この木の i 番目の辺は、2 頂点 a_i,b_i を結んでいます (1\leq i\leq N-1) 。
はじめ、頂点 1 に駒が置いてあり、あなたはこれから、以下の操作をちょうど N 回行います。
- その時点で駒が置かれておらず、かつ今までの操作で一度も選択されていない頂点を 1 つ選び、 駒を選んだ頂点の方向に 1 つ動かす。
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
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 1 → 2 → 1 → 2 → 4. 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