#6066. 「2017 山东一轮集训 Day3」第二题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

对于一棵有根树,定义一个点 u k \text{ −} 子树为 u 的子树中距离 u 不超过 k 的部分。注意,假如 u 的子树中不存在距离 u k 的点,则 u k \text{ −} 子树是不存在的。

定义两棵子树是相同的,当且仅当不考虑点的标号时,他们的形态是相同的(儿子的顺序也需要考虑)。给定一棵 n 个点,点的标号在 [1, n] ,以 1 为根的有根树。问最大的 k ,使得存在两个点 u \neq v ,满足 u k \text{ −} 子树与 v k \text{ −} 子树相同。

输入格式

第一行输入一个正整数 n
接下来读入 n 个部分,第 i 个部分描述点 i 的儿子,且以顺序给出。
每个部分首先读入一个整数 x ,代表儿子个数。接下来 x 个整数,代表从左到右儿子的标号。

输出格式

输出一个整数 k ,代表最大的合法的 k

样例

样例输入

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

样例输出

3

数据范围与提示

对于 20\% 的数据, n \leq 100
对于 40\% 的数据, n \leq 2000
对于 60\% 的数据, n \leq 30000
对于 100\% 的数据, n \leq 100000 ,保证给出的树是合法的。