← 返回题目列表

Codeforces · 120/F

F. 蜘蛛

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

有一天,妈妈让 Petya 对他的玩具进行分类并扔掉其中一些。彼佳发现了一整盒玩具蜘蛛。它们对他来说非常珍贵,男孩不想扔掉它们。佩蒂亚想出了一个狡猾的计划:他将所有蜘蛛粘在一起,然后将它们固定在天花板上。此外,佩蒂亚知道蜘蛛挂得越低,妈妈就越喜欢它,然后她就不会扔掉他最喜欢的玩具。帮助彼佳执行计划。

蜘蛛由 k 个珠子组成,这些珠子通过 k - 1 条线绑在一起。每条线连接两个不同的珠子,组成蜘蛛的任何一对珠子要么直接通过线连接,要么通过一些线和珠子链连接。

Petya 可以直接将蜘蛛的珠子粘在一起。每根线的长度等于1。珠子的大小可以忽略不计。这就是为什么我们可以认为蜘蛛的粘合是通过识别一些珠子来发生的(见图)。此外,由粘合过程产生的结构也应该代表蜘蛛,即它应该具有给定的特征。

Petya 将所有蜘蛛粘在一起后,他测量了所得玩具的长度。一对珠子之间的距离被确定为连接这两个珠子的螺纹的总长度。所得结构的长度是所有珠子对之间的最大距离。 Petya想要制作长度尽可能长的蜘蛛。

图二显示了第二个样本中的两只蜘蛛。我们可以将第二个蜘蛛的 1 号珠子粘到第一个蜘蛛的 2 号珠子上。形成最大长度线序列的蜘蛛中的线在图片上突出显示。

输入

第一个输入文件行包含一个整数 n (1 ≤ n ≤ 100) — 蜘蛛的数量。接下来的 n 行包含每个蜘蛛的描述:整数 ni (2 ≤ ni ≤ 100) — 珠子的数量,然后 ni - 1 对数字表示通过线连接的珠子的数量。组成每只蜘蛛的珠子从 1 到 ni 编号。

输出

打印一个数字——所需结构的长度。

示例

输入 #1

1
3 1 2 2 3

输出 #1

2

输入 #2

2
3 1 2 1 3
4 1 2 2 3 2 4

输出 #2

4

输入 #3

2
5 1 2 2 3 3 4 3 5
7 3 4 1 2 2 4 4 6 2 7 6 5

输出 #3

7