Making Friends

Time Limit: 5000 ms

Memory Limit: 65535 ms

Description

The national college entrance examination has ended and a new semester is coming. Thousands of new students are coming into NJUST to have their university life. As you know, some of them are from the same place so that they know each other before they reach NJUST while some others are still lonely. As a senior student, you should help them to adjust themselves to university life. The most important is to make friends with other freshmen. So you need to make a survey to find out the maximum set satisfying the condition: there are no two students in the set know each other. This will help you to decide how you do the job later.

Input

The input contains several data sets. Each data set represents one set of subjects of the study, with the following description: The first line contains the number of students (N). Then following N lines, each contains the information of each student, in the following format The number of students he/she knows (M): student_id1 student_id2 student_id3 ...student_idM (If somebody knows no one else, then M will be 0.) NOTICE: The student_id is an integer number between 0 and n-1 (n <=500).

Output

For each given data set, the program should output a line containing the result.

Sample Input

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

Sample Output

5
2

Hint

Source

SuYing & LuFei

提交代码