题目描述

研究员鹿鸣在分析一张有向关系图。图中有 $n$ 个点，编号为 $1$ 到 $n$，以及 $m$ 条有向边。她想找到所有点的排列

$$p_1,p_2,\ldots,p_n$$

满足一个非常严格的规则：

对于任意 $1\le i<j\le 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$，表示测试用例数量。

对于每个测试用例，第一行包含两个整数 $n,m$，表示点数和边数。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示图中有一条从 $u$ 指向 $v$ 的有向边。

图中可能存在重边。

输出格式

对于每个测试用例，第一行输出满足条件的排列数量对 $10^9+7$ 取模后的结果。

如果满足条件的排列实际数量不超过 $n$，再输出一行，按字典序从小到大输出所有这些排列的值，数之间用一个空格分隔。

如果排列数量大于 $n$，或者没有满足条件的排列，则不需要输出额外的空行。

数据范围

• $1\le T\le 10^5$；
• $n\ge 1$；
• $m\ge 0$；
• 所有测试用例的 $n$ 之和不超过 $5\cdot 10^5$；
• 所有测试用例的 $m$ 之和不超过 $10^6$；
• $1\le u,v\le n$，且 $u\ne v$。

样例 1

输入

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

输出

2
13425 34251