19024번 - Hamilton Path 다국어

문제

You are given a directed graph with $n$ vertices and $m$ edges. The vertices are labeled from 1ドル$ to $n$. You need to find all the permutations of vertices $p_1, p_2, \ldots, p_n$ satisfying the following constraint:

• For all 1ドル \leq i < j \leq n,ドル an edge $(p_i, p_j)$ exists if and only if $j = i + 1$.

We define the value of a permutation $p_1, p_2, \ldots, p_n$ as $$\left(\sum_{i = 1}^n p_i \cdot 10^{n - i}\right) \bmod (10^9 + 7)\text{.}$$

Output the number of such permutations modulo 10ドル^9 + 7$. If the number of such permutations is not greater than $n,ドル you also need to consider them all in lexicographical order, and output their values in this order.

입력

The first line contains an integer $T$ ($T \leq 10^5$) indicating the number of test cases.

For each test case, the first line contains two integers $n$ and $m$ ($n \geq 1,ドル $m \geq 0,ドル 1ドル \leq \sum n \leq 5 \cdot 10^5,ドル 1ドル \leq \sum m \leq 10^6$).

Each of the following $m$ lines contains two integers $u$ and $v$ (1ドル \leq u, v \leq n,ドル $u \neq v$) indicating that there is a directed edge from $u$ to $v$ in the graph. Note that the graph can contain parallel edges.

출력

For each test case, output the number of the permutations modulo 10ドル^9 + 7$ in the first line. If the number of permutations is not greater than $n,ドル print another line with space-separated values of all the permutations, considered in lexicographical order. You \textbf{don't need to} output an empty line if the number is greater than $n$ or there is no solution.

제한

힌트