#P15725. 禁边巡游序

禁边巡游序

题目描述

研究员鹿鸣在分析一张有向关系图。图中有 nn 个点,编号为 11 到 nn,以及 mm 条有向边。她想找到所有点的排列

p1,p2,…,pnp_1,p_2,\ldots,p_n

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

对于任意 1≤i<j≤n1\le i<j\le n,有向边 (pi,pj)(p_i,p_j) 存在,当且仅当

j=i+1.j=i+1.

也就是说,在这个排列中,一个较早出现的点指向较晚出现的点,只有在它们相邻时才允许发生;相邻的每一对则必须有这条边。

对于一个排列 p1,p2,…,pnp_1,p_2,\ldots,p_n,定义它的值为

$$\left(\sum_{i=1}^n p_i\cdot 10^{n-i}\right)\bmod (10^9+7).$$

你需要输出满足条件的排列数量对 109+710^9+7 取模后的结果。如果满足条件的排列实际数量不超过 nn,还需要按字典序从小到大列出这些排列对应的值。

输入格式

第一行包含一个整数 TT,表示测试用例数量。

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

接下来 mm 行,每行包含两个整数 u,vu,v,表示图中有一条从 uu 指向 vv 的有向边。

图中可能存在重边。

输出格式

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

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

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

数据范围

  • 1≤T≤1051\le T\le 10^5;
  • n≥1n\ge 1;
  • m≥0m\ge 0;
  • 所有测试用例的 nn 之和不超过 5⋅1055\cdot 10^5;
  • 所有测试用例的 mm 之和不超过 10610^6;
  • 1≤u,v≤n1\le u,v\le n,且 u≠vu\ne v。

样例 1

输入

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

输出

2
13425 34251