给定一个包含 $n$ 个顶点和 $m$ 条边的有向图。顶点编号从 $1$ 到 $n$。你需要找到所有满足以下约束条件的顶点排列 $p_1, p_2, \dots, p_n$：

• 对于所有 $1 \le i < j \le n$，存在边 $(p_i, p_j)$ 当且仅当 $j = i + 1$。

我们定义排列 $p_1, p_2, \dots, p_n$ 的值为： $$\left( \sum_{i=1}^{n} p_i \cdot 10^{n-i} \right) \pmod{10^9 + 7}$$

输出满足条件的排列数量，对 $10^9 + 7$ 取模。如果满足条件的排列数量不大于 $n$，你还需要将它们按字典序排列，并按此顺序输出它们的值。

输入格式

第一行包含一个整数 $T$ ($T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$ ($n \ge 1, m \ge 0, 1 \le \sum n \le 5 \cdot 10^5, 1 \le \sum m \le 10^6$)。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示图中存在一条从 $u$ 到 $v$ 的有向边。注意，图中可能包含重边。

输出格式

对于每个测试用例，第一行输出满足条件的排列数量，对 $10^9 + 7$ 取模。如果满足条件的排列数量不大于 $n$，则在下一行按字典序输出所有排列的值，用空格分隔。如果数量大于 $n$ 或者没有解，则不需要输出空行。

样例

输入 1

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

输出 1

2
13425 34251