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