E. Planar Exact Cover
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The farmers' market has $$$N$$$ stalls and $$$M$$$ storage barns on a two-dimensional plane. There are $$$6M$$$ roads, each connecting a stall to a storage barn, such that no two roads intersect except at endpoints. In other words, the stalls and barns form a planar bipartite graph. Furthermore, every storage barn is connected to exactly $$$6$$$ distinct stalls.

Busy Beaver wants to select a subset of storage barns such that every stall is connected to exactly one selected barn by a road. How many ways are there to choose such a subset? As the answer may be large, output it modulo $$$10^9+7$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$6 \le N \le 3 \cdot 10^5$$$, $$$N/6 \le M \le 10^5$$$, $$$N \equiv 0 \pmod 6$$$), the number of stalls and the number of barns, respectively.

The $$$i$$$-th of the next $$$M$$$ lines starts with the integer $$$6$$$, followed by $$$6$$$ distinct integers $$$a_{i1},\dots,a_{i6}$$$ ($$$1 \le a_{ij} \le N$$$ for all $$$1 \le j \le 6$$$), describing the stalls connected to the $$$i$$$-th barn in clockwise order.

The $$$i$$$-th of the next $$$N$$$ lines starts with an integer $$$d_i$$$ ($$$1 \le d_i \le M$$$), followed by $$$d_i$$$ distinct integers $$$b_{i1},\dots,b_{id_i}$$$ ($$$1 \le b_{ij} \le M$$$ for all $$$1 \le j \le d_i$$$), describing the barns connected to the $$$i$$$-th stall in clockwise order.

It is guaranteed that the input describes a valid planar combinatorial embedding.

The sum of $$$N$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

The sum of $$$M$$$ across all test cases does not exceed $$$10^5$$$.

Output

Output a single integer for each test case: the number of ways, modulo $$$10^9+7$$$.

Scoring

There are two subtasks for this problem.

  • ($$$50$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$3 \cdot 10^3$$$, and the sum of $$$M$$$ across all test cases does not exceed $$$10^3$$$.
  • ($$$50$$$ points): No additional constraints.
Example
Input
2
12 4
6 1 2 3 4 5 6
6 7 8 9 10 11 12
6 4 3 2 1 12 11
6 10 9 8 7 6 5
2 1 3
2 1 3
2 1 3
2 1 3
2 1 4
2 1 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 3
2 2 3
12 4
6 1 2 3 4 5 6
6 6 7 8 9 10 11
6 1 12 6 11 10 9
6 8 7 6 5 4 3
2 1 3
1 1
2 1 4
2 1 4
2 1 4
4 1 4 2 3
2 2 4
2 2 4
2 2 3
2 2 3
2 2 3
1 3
Output
2
0
Note

In the first test case, the barns and stalls are as follows:

There are $$$2$$$ ways to select the subset: either choosing barns $$$1$$$ and $$$2$$$, or choosing barns $$$3$$$ and $$$4$$$.

In the second test case, the barns and stalls are as follows:

Note that the barns connected to stall $$$6$$$ are listed in clockwise order: $$$1, 4, 2, 3$$$. There are no ways to select a subset of barns such that every stall is connected to exactly one selected barn.