<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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:
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.

Input
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.

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

Example(s)
sample input
sample output
5 2
2 1 3
3 3 4 5
3



Note
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.

<|response|>
## 1) Abridged problem statement (concise)

There are **N resources** and **M users**. User *i* requests access to a set \(S_i\) of resources.

We must create some **user groups**. Each group contains:
- a set of users \(U_g\)
- a set of resources \(R_g\)

Rules:
1. A resource can belong to **at most one** group (resource sets of groups are disjoint).
2. A user can access a resource iff they are in the group that contains it.
3. Each user must access **exactly** the resources they requested (no missing and no extra).
4. A user may belong to multiple groups.

Find the **minimum number of groups** needed.

---

## 2) Key observations

### Observation A: Each resource forces a specific user set
For a resource \(r\), define:
\[
U(r) = \{\, u \mid u \text{ requests } r \,\}
\]
If resource \(r\) is placed into some group \(g\), then by rule (2) all users in \(U_g\) get access to \(r\).  
By rule (3) **exactly** the users in \(U(r)\) must have access to \(r\). Therefore:
\[
U_g = U(r)
\]
So the user membership of the group containing \(r\) is **fully determined**.

### Observation B: Two resources can share a group iff their user-sets match
If two resources \(r_1\) and \(r_2\) are in the same group, the group’s user set must equal both \(U(r_1)\) and \(U(r_2)\). Hence:
\[
r_1, r_2 \text{ can be in the same group } \iff U(r_1) = U(r_2)
\]

### Observation C: Unrequested resources need no group
If \(U(r)=\emptyset\) (nobody requests resource \(r\)), we can put it in **no group**. It doesn’t affect any user’s access requirements.

**Conclusion:**  
The minimum number of groups equals the number of **distinct non-empty** sets \(U(r)\) across all resources.

---

## 3) Full solution approach

1. Create an array `resource_users[r]` listing which users request resource `r`.
2. Read each user’s requested resources; for each resource `r` in user `u`’s list, append `u` to `resource_users[r]`.
3. For each resource `r`:
   - If `resource_users[r]` is non-empty:
     - sort it (canonical representation of the set)
     - insert it into a set of vectors/tuples to deduplicate equal user-sets
4. Output the size of that set.

**Complexity:**  
- Building lists: \(O(\text{total requests}) \le 10^4\) (since \(N,M \le 100\))
- Sorting user lists: \(O(N \cdot M \log M)\) at worst, tiny for constraints  
Well within limits.

---

## 4) C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<vector<int>> resource_users;

void read() {
    cin >> n >> m;
    resource_users.resize(n + 1);

    for(int u = 1; u <= m; u++) {
        int k;
        cin >> k;
        for(int j = 0; j < k; j++) {
            int r;
            cin >> r;
            resource_users[r].push_back(u);
        }
    }
}

void solve() {
    // The solution is fairly simple - we can just check for every file the set
    // of people that should have access to it. We don't want any other person
    // to have access to the same file, so this corresponds to a group. The only
    // way to share groups is if there is another file with the same set of
    // people. We can simply sort the ids of the people that should have access
    // to every file, and then sort all of these - the number of groups will be
    // the number of unique vectors.

    set<vector<int>> unique_groups;
    for(int r = 1; r <= n; r++) {
        if(!resource_users[r].empty()) {
            sort(resource_users[r].begin(), resource_users[r].end());
            unique_groups.insert(resource_users[r]);
        }
    }

    cout << unique_groups.size() << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)

    N = int(next(it))
    M = int(next(it))

    # resource_users[r] = list of users who request resource r (1..N)
    resource_users = [[] for _ in range(N + 1)]

    # Read each user's request set and record user IDs per resource
    for u in range(1, M + 1):
        k = int(next(it))
        for _ in range(k):
            r = int(next(it))
            resource_users[r].append(u)

    # Deduplicate user-sets; store as sorted tuples (hashable)
    unique_user_sets = set()
    for r in range(1, N + 1):
        if resource_users[r]:  # ignore empty sets (unrequested resources)
            unique_user_sets.add(tuple(sorted(resource_users[r])))

    print(len(unique_user_sets))

if __name__ == "__main__":
    main()
```

These implementations directly apply the core idea: **resources with the same set of requesting users can be grouped together; different sets require different groups**.