题目描述

有 $n$ 个犯罪团伙，编号为 $1\sim n$。某些团伙之间有直接联系，初始时所有团伙通过直接或间接的联系构成一个连通的犯罪集团。

一个集团的危险程度等于其中团伙的数量。警方将按编号顺序打击掉 $1,2,\ldots,k$ 号团伙，同时删除与这些团伙相关的联系。

求最小的 $k$，使剩余的每个连通集团都至多有 $\lfloor n/2\rfloor$ 个团伙。

输入格式

第一行一个整数 $n$。接下来 $n$ 行，第 $i$ 行先给出一个整数，表示这一行后面有多少个编号；随后给出与 $i$ 号团伙直接联系的团伙编号。所有联系是双向的。

输出格式

输出最小的 k。

样例

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

1

数据范围

$1\le n\le1000$。初始图连通，无自环和重复联系。