Employee Project Assignment

You are given M employees and N projects. Each employee has a set of skills, and each project has a list of required skills. Your task is to count the number of ways to assign each employee to exactly one project such that every project has at least one employee with the required skills.

Formally, let \(E = \{1,2,\ldots,M\}\) be the set of employees and \(P = \{1,2,\ldots,N\}\) be the set of projects. For each employee \(e\), there is a skill set \(S_e\); and for each project \(p\), there is a requirement set \(R_p\). An assignment is a function \(f: E \to P\) (each employee is assigned one project). An assignment is considered valid if for every project \(p \in P\), there exists at least one employee \(e\) such that \(f(e)=p\) and \(R_p \subseteq S_e\) (in other words, the employee's skills cover the project’s requirements).

Your program should read from standard input and write the answer to standard output. The answer is simply the count of valid assignments.

inputFormat

The first line contains two integers M and N separated by a space, where M is the number of employees and N is the number of projects.

This is followed by M lines. Each of these lines starts with an integer representing the number of skills the employee has, followed by that many integers representing the skills.

After that, there are N lines describing the projects. Each project description starts with an integer representing the number of required skills, followed by that many integers.

Input is provided via standard input (STDIN).

outputFormat

Output a single integer - the number of valid assignments, printed to standard output (STDOUT).

3 2
3 1 2 3
2 2 3
1 4
2 1 2
1 4

2