Time limit per test: 0.25
Memory limit: 65536
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
users numbered 1, 2,..., M
Let the user i
require an access to the finite set of the resources Si
,... }. 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
,... } be the finite set of users associated with the group g
. Let Rg
,... } 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:
- No two different user groups can have common resources, i.e. each resource can belong to at most one user group.
- A user has an access to a resource if this user belongs to the user group containing this resource.
- Each user should have access to all resources he or she wishes, but to no any other resource.
- A user can belong to any number of 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
(1 ≤ N
≤ 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.
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.