해밀턴 경로

방향 그래프가 $n$개의 정점과 $m$개의 간선으로 주어진다. 정점은 $1$부터 $n$까지 번호가 매겨져 있다. 다음 조건을 만족하는 정점의 순열 $p_1, p_2, \ldots, p_n$을 모두 구하라.

• 모든 $1 \leq i < j \leq n$에 대해, 간선 $(p_i, p_j)$가 존재할 필요충분조건은 $j = i + 1$이다.

순열 $p_1, p_2, \ldots, p_n$의 값을 $\left(\sum_{i = 1}^n p_i \cdot 10^{n - i}\right) \bmod (10^9 + 7)$로 정의한다.

조건을 만족하는 순열의 개수를 $10^9 + 7$로 나눈 나머지를 출력하라. 개수가 $n$ 이하이면, 순열을 사전순으로 정렬했을 때의 값도 그 순서대로 출력하라.

첫 줄에 테스트 케이스의 개수 $T$ ($T \leq 10^5$)가 주어진다.

각 테스트 케이스의 첫 줄에 정수 $n$, $m$ ($n \geq 1$, $m \geq 0$, $1 \leq \sum n \leq 5 \cdot 10^5$, $1 \leq \sum m \leq 10^6$)이 주어진다. 이어지는 $m$개의 줄에는 정수 $u$, $v$ ($1 \leq u, v \leq n$, $u \neq v$)가 주어지며, 이는 $u$에서 $v$로 가는 방향 간선이 있다는 뜻이다. 평행 간선이 있을 수 있다.

각 테스트 케이스마다 첫 줄에 순열의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다. 순열의 개수가 $n$ 이하이면, 다음 줄에 모든 순열의 값을 사전순으로 공백으로 구분하여 출력한다. 개수가 $n$보다 크거나 해가 없으면 빈 줄을 출력할 필요가 없다.