← 返回题目列表

AtCoder · abc394_f

I. 烷烃

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

分数: 500 点

问题陈述

给你一棵无向树 T 与 N 顶点,编号 1, 2, \ldots, N。的 i-th 边是连接顶点的无向边 A_i 和 B_i.

图被定义为 烷烃 当且仅当满足以下条件:

  • 该图是一棵无向树。
  • 每个顶点都有度数 1 or 4,并且至少有一个度数顶点 4.

判断是否存在子图 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