시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

1
5 6
3 4
2 5
5 3
1 3
4 2
5 1

예제 출력 1

2
13425 34251