J. Problematic Paths
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There is a directed graph with $$$n$$$ vertices and $$$m$$$ edges, as well as $$$k$$$ arrays $$$a_1, a_2, \ldots, a_k$$$.

A good path from vertex $$$1$$$ to vertex $$$n$$$ of length $$$s$$$ is defined as a sequence of vertices $$$p_1, p_2, \ldots, p_s$$$ ($$$1 \le s \le n$$$) that satisfies the following conditions:

  • $$$1 = p_1 \lt p_2 \lt \ldots \lt p_{s-1} \lt p_s = n$$$; for any $$$i \in \{1,2,\ldots,s-1\}$$$, there is an edge from vertex $$$p_i$$$ to vertex $$$p_{i+1}$$$.
  • For no pair $$$1 \le l \le r \le s$$$ and index $$$j \in \{1,2,\ldots,k\}$$$, the array $$$p_l, p_{l+1}, \ldots, p_r$$$ isn't the same as the array $$$a_j$$$.

Your task is to compute the number of good paths modulo $$$10^9+7$$$.

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The following describes the test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$1 \le m, k \le 3 \cdot 10^5$$$) — the number of vertices and edges in the graph and the number of arrays.

Next, there are $$$m$$$ lines, the $$$i$$$-th of which contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i \lt v_i \le n$$$) — the start and end of the $$$i$$$-th edge.

Next, there are $$$k$$$ lines, the $$$i$$$-th of which contains an integer $$$l_i$$$ and $$$l_i$$$ integers $$$a_{i,1}, \ldots, a_{i,l_i}$$$ ($$$1 \le l_i \le n$$$, $$$1 \le a_1 \lt a_2 \lt \ldots \lt a_{l_i} \le n$$$) — the length of the array $$$a_i$$$ and its elements.

It is guaranteed that the sum of $$$n$$$, the sum of $$$m$$$, and the sum of $$$k$$$ across all test cases do not exceed $$$3 \cdot 10^5$$$.

It is guaranteed that the sum of $$$l_i$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer — the number of good paths modulo $$$10^9 + 7$$$.

Example
Input
3
5 7 4
1 2
2 3
3 4
4 5
1 3
2 4
3 5
2 1 2
2 2 3
2 3 4
2 4 5
5 7 3
1 2
2 3
3 4
4 5
1 3
2 4
3 5
3 1 2 3
3 2 3 4
3 3 4 5
6 9 4
1 2
2 3
3 4
4 5
5 6
1 3
2 4
3 5
4 6
3 1 2 3
3 2 3 4
3 3 4 5
3 4 5 6
Output
1
2
3
Note

In the first example, the only good path is $$$1 \to 3 \to 5$$$.

In the second example, the only good paths are $$$1 \to 2 \to 4 \to 5$$$ and $$$1 \to 3 \to 5$$$.

In the third example, the good paths are $$$1 \to 2 \to 4 \to 6$$$, $$$1 \to 3 \to 4 \to 6$$$, and $$$1 \to 3 \to 5 \to 6$$$.