题目描述

给你一个 $n$，请你输出 $1 \sim n$# 「2017 山东一轮集训 Day3」第二题

传统 1000 ms 512 MiB

$146$ 通过 $528$ 提交

题目描述

对于一棵有根树，定义一个点 $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$，保证给出的树是合法的。。

输入格式

一个数 $n$。

输出格式

一行 $n$ 个数，为 $1 \sim n$。

5

1 2 3 4 5

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10^7$。