Criminal Gangs

Special for beginners, ^_^

Problem Description

A region has $n$ criminal gangs ($n\le1000$). The local police number them $1\sim n$ in decreasing order of dangerousness. Some gangs are directly connected, but any two gangs can be connected directly or indirectly, so they form one huge criminal syndicate. The dangerousness of a syndicate is determined solely by the number of gangs inside it, regardless of the dangerousness of any individual gang (so this syndicate's dangerousness is $n$).

Now the police want to spend as little time as possible (that is, crack down on as few gangs as possible) so that the huge syndicate breaks into several smaller syndicates, and the dangerousness of the largest of them does not exceed $n/2$. For the best effect they will crack down on the gangs numbered $1$ through $k$ in order. Write a program to find the minimum value of $k$.

Input Format

The first line is a positive integer $n$. The next $n$ lines each contain several positive integers; the first integer states how many integers follow it on that line. If a positive integer $k$ appears on line $i$, it means gangs $i$ and $k$ are directly connected.

Output Format

A positive integer: the minimum value of $k$.

Sample Input 1

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

Sample Output 1

1

Hint

Output 1 (crack down on the criminal gangs).

Constraints

1s, 1024KiB for each test case.