F - Alkane Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点の無向木 T が与えられます。頂点には 1, 2, \ldots, N の番号が付いており、i 番目の辺は頂点 A_i と頂点 B_i を結ぶ無向辺です。

グラフがアルカンであるとは以下の条件をともに満たしていることであると定義します。

  • グラフは無向木である
  • すべての頂点の次数が 1 または 4 であり、次数 4 の頂点が 1 つ以上存在する

T の部分グラフであってアルカンであるものが存在するか判定し、存在する場合はそのようなものの頂点数の最大値を求めてください。

制約

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

出力

T の部分グラフであってアルカンであるものが存在する場合はそのようなものの頂点数の最大値を出力せよ。そうでない場合は -1 と出力せよ。

入力例 1

9
1 2
2 3
3 4
4 5
2 6
2 7
3 8
3 9

出力例 1

8

頂点 u と頂点 v を結ぶ無向辺を辺 (u, v) と表記します。

頂点 1,2,3,4,6,7,8,9、辺 (1,2),(2,3),(3,4),(2,6),(2,7),(3,8),(3,9) からなる部分グラフはアルカンです。

入力例 2

7
1 2
1 3
2 4
2 5
3 6
3 7

出力例 2

-1

入力例 3

15
8 5
2 9
1 12
6 11
9 3
15 1
7 12
7 13
10 5
6 9
5 1
1 9
4 5
6 14

出力例 3

11

Score : 500 points

Problem Statement

You are given an undirected tree T with N vertices, numbered 1, 2, \ldots, N. The i-th edge is an undirected edge connecting vertices A_i and B_i.

A graph is defined to be an alkane if and only if it satisfies the following conditions:

  • The graph is an undirected tree.
  • Every vertex has degree 1 or 4, and there is at least one vertex of degree 4.

Determine whether there exists a subgraph of T that is an alkane, and if so, find the maximum number of vertices in such a subgraph.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • The given graph is an undirected tree.
  • All input values are integers.

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

If there exists a subgraph of T that is an alkane, print the maximum number of vertices in such a subgraph. Otherwise, print -1.

Sample Input 1

9
1 2
2 3
3 4
4 5
2 6
2 7
3 8
3 9

Sample Output 1

8

Let (u, v) denote an undirected edge between vertices u and v.

A subgraph consisting of vertices 1,2,3,4,6,7,8,9 and edges (1,2),(2,3),(3,4),(2,6),(2,7),(3,8),(3,9) is an alkane.

Sample Input 2

7
1 2
1 3
2 4
2 5
3 6
3 7

Sample Output 2

-1

Sample Input 3

15
8 5
2 9
1 12
6 11
9 3
15 1
7 12
7 13
10 5
6 9
5 1
1 9
4 5
6 14

Sample Output 3

11