Given a set of sets, how can we determine if they satisfy the conditions in the Problem Statement?
The decision problem can be solved as follows.

• We have a set \(T\) of integers, initialized as an empty set.
• Let \(s_1, s_2, \dots, s_k\) be the chosen set. Perform the following operation on \(i=1, 2, \dots, k\).
  • Add to \(T\) all the integers contained in \(s_i\). (If an integer is already added to \(T\), it is not added twice.)
• After the operations above are completed, the answer is Yes if \(T\) contains all of \(1, 2, \dots, N\), and No otherwise.

This algorithm works in a total of \(\mathrm{O}(N M \log N)\) by managing \(T\) with a set type like a std::set in C++ or the “dict” type in Python. Thus, if we can solve the decision problem for all the \(2^M-1\) ways of choice, the problem can be solved in a total of \(\mathrm{O}(2^M N M \log N)\) time.

We can enumerate all the ways to choose the sets with a technique called bit bruteforcing.
(Here, we assume that the sets are indexed 0-based: \(S_0, S_1, \dots, S_{M-1}\).) The bit bruteforcing is a method to enumerate the choices of sets by associating each them with an integer \(x\) between \(0\) and \(2^M-1\) (inclusive), as follows:

• (The \(0\)-th bit of \(x\) in binary is \(1\)) \(\iff\) (Set \(S_0\) is chosen)
• (The \(1\)-th bit of \(x\) in binary is \(1\)) \(\iff\) (Set \(S_1\) is chosen)
• \(\vdots\)
• (The \((M-1)\)-th bit of \(x\) in binary is \(1\)) \(\iff\) (Set \(S_{M-1}\) is chosen)

(Here, “the \(i\)-th bit” refers to the \(2^i\)s place in binary.)
For example, if \(M = 3\) and \(x = 3\), then \(3\) in base three is 011, so we choose \(S_0\) and \(S_1\) here.

Such a correspondence allows us to map every way to choose sets to every integer between \(0\) and \(2^M-1\). For example, if \(M=3\), then the integers between \(0\) and \(2^3-1 = 7\) are, in base 2, as follows:

000
001
010
011
100
101
110
111

As you can see in the example above, every way to choose sets has a corresponding integer within the range. For example, choosing \(S_0\) and \(S_2\) corresponds to a base-2 integer 101, which corresponds to \(5\).)

With such a correspondence, we can scan every integer between \(0\) and \(2^M-1\) without a for loop and convert the integer into a set, in order to inspect all the ways to choose without duplicates. Also, extracting the \(i\)-th bit of the integer \(x\) can be found as (x >> i) & 1 thanks to the right-shift and logical product operators, which enables us to convert from an integer to a set correctly.

With the bit-bruteforcing described above, the problem can be solved in a total of \(\mathrm{O}(2^M N M \log N)\) time.

Sample code (C++):

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> a(M);
  for (int i = 0; i < M; i++) {
    int c;
    cin >> c;
    a[i].resize(c);
    for (auto& x : a[i]) cin >> x;
  }
  int ans = 0;
  for (int b = 0; b < (1 << M); b++) {
    set<int> s;
    for (int i = 0; i < M; i++) {
      if ((b >> i) & 1) {
        for (auto& x : a[i]) s.insert(x);
      }
    }
    ans += (int)s.size() == N;
  }
  cout << ans << "\n";
}