Knight of Diamonds, wielding contractions to forge a tree of perfect face.
对于一棵有标号无根树,定义一次 收缩 操作
- 如果
在当前树上不相邻则无事发生。 - 否则如果
相邻,对于 的所有非 的邻居,将其和 之间连一条无向边,然后删除 和所有与其相连的边。
定义一棵有标号无根树为 无根满二叉树,当且仅当其可以通过选择一个结点作为根成为 满二叉树。
现在给定一棵大小为
可以证明始终存在一棵大小有限的无根满二叉树满足题目限制。
由于答案可能很大,假设答案为
(一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的高度为
输入格式
第一行一个正整数
第一行输入一个正整数
。接下来
行,每行两个正整数 表示 上的一条边 。
输出格式
对于每组测试数据,输出一行一个正整数表示答案。
样例一
input
1 5 1 5 2 5 3 5 4 5
output
3
explanation
可以通过大小为
样例二
input
2 3 1 2 1 3 7 1 2 2 3 1 4 1 5 5 6 3 7
output
2 4
样例三~七
见附件下载。
限制与约定
对于所有数据,保证
子任务编号 | 树形态 | 分值 | ||
---|---|---|---|---|
1 | 无特殊形态 | 15 | ||
2 | 无特殊形态 | 15 | ||
3 | 链 | 10 | ||
4 | 菊花 | 10 | ||
5 | 无特殊形态 | 25 | ||
6 | 无特殊形态 | 25 |
“树形态”中,“菊花”指存在一个向所有点有直接连边的点,“链”指所有点度数不超过
时间限制:
空间限制: