318. Grants

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

Berland City Central School has a lot of computers connected to the network. The network has a number of shared network resources and a number of users willing to access these resources. There are N resources numbered 1, 2,..., N and M users numbered 1, 2,..., M.

Let the user i require an access to the finite set of the resources Si = {ri1, ri2,... }. System administrator needs to grant each user each resource he or she wishes. The solution he chose is to use user groups.

User group is an object that allows to link users and resources. Each user group is associated with an arbitrary number of users and resources. Let Ug = {uj1, uj2,... } be the finite set of users associated with the group g. Let Rg = {rk1, rk2,... } be the finite set of resources associated with the same group g.

The system administrator should obey the following rules while creating the user groups:

Your task is to help the system administrator to create the user groups in such a way that the rules above are satisfied and the number of user groups is minimal.

The first line of the input contains two integer numbers N and M (1 ≤ N, M≤ 100). Each of the following M lines contains the description of Si. Each description consists of the size of Si (non-negative integer not exceeding N) followed by the items of Si (different positive integers not exceeding N). Numbers in each line are separated by one or several spaces.

Write the minimal number of the user groups required to the output.

sample input
sample output
5 2
2 1 3
3 3 4 5

You need at least three user groups to grant desired access privileges to each user. For example, first group may contain first user and first object. Second group may contain both users and third object. Third group may contain second user and fourth and fifth objects.

Online Contester Team © 2002 - 2010. All rights reserved.