J. Проблемные пути
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть ориентированный граф из $$$n$$$ вершин и $$$m$$$ рёбер, а так же есть $$$k$$$ массивов $$$a_1, a_2, \ldots, a_k$$$.

Хорошим путём из вершины $$$1$$$ в вершину $$$n$$$ длины $$$s$$$ назовем последовательность вершин $$$p_1, p_2, \ldots, p_s$$$ ($$$1 \le s \le n$$$), которая удовлетворяет следующим условиям:

  • $$$1 = p_1 \lt p_2 \lt \ldots \lt p_{s-1} \lt p_s = n$$$, для любого $$$i \in \{1,2,\ldots,s-1\}$$$ есть ребро из вершины $$$p_i$$$ в вершину $$$p_{i+1}$$$.
  • Ни для какой пары $$$1 \le l \le r \le s$$$ и индекса $$$j \in \{1,2,\ldots,k\}$$$ массив $$$p_l, p_{l+1}, \ldots, p_r$$$ не совпадает с массивом $$$a_j$$$.

Ваша задача заключается в том, чтобы вычислить количество хороших путей по модулю $$$10^9+7$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$1 \le m, k \le 3 \cdot 10^5$$$) — количество вершин и рёбер в графе и количество массивов.

Далее следуют $$$m$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i \lt v_i \le n$$$) — начало и конец $$$i$$$-го ребра.

Далее следует $$$k$$$ строк, $$$i$$$-я из которых содержит целое число $$$l_i$$$ и $$$l_i$$$ целых чисел $$$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$$$) — длина массива $$$a_i$$$ и его элементы.

Гарантируется, что сумма $$$n$$$, сумма $$$m$$$ и сумма $$$k$$$ по всем наборам входных данных не превосходят $$$3 \cdot 10^5$$$.

Гарантируется, что сумма $$$l_i$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — количество хороших путей по модулю $$$10^9 + 7$$$.

Пример
Входные данные
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
Выходные данные
1
2
3
Примечание

В первом примере хорошим является только путь $$$1 \to 3 \to 5$$$.

Во втором примере хорошим являются только пути $$$1 \to 2 \to 4 \to 5$$$ и $$$1 \to 3 \to 5$$$.

В третьем примере хорошими являются пути $$$1 \to 2 \to 4 \to 6$$$, $$$1 \to 3 \to 4 \to 6$$$, $$$1 \to 3 \to 5 \to 6$$$.