题目描述

本题中涉及到的图论定义：

• 一个 $n$ 个点，点的编号为 $1,2,\dots,n$ 的有向图 $G=(V,E)$ 的拓扑序是一个 $1,2,\dots,n$ 的排列 $p$，且若 $E$ 中存在 $x\to y$ 的边，就有 $p$ 中 $x$ 出现在 $y$ 之前。

今天，算法竞赛机器人小 G 学习了拓扑排序相关知识。凭着强大的机器学习本领，它很快便一并学会了如何计算一个有向无环图的拓扑序个数。接着，它开始思考一个拓展问题：给定一个有向无环图 $G$ 和两个 $G$ 中的点 $u,v$，请你求出有多少种 $G$ 的拓扑序满足 $u$ 排在 $v$ 之前。

你知道稍加思考后小 G 也能秒掉这题。不巧，就在这时停电了，依靠插头进食的小 G 也因此停止工作了。所以你只好自己解决这个拓展问题了。

为了让问题更富有挑战性，设 $G$ 中总点数为 $n$，请你对所有 $n(n-1)$ 对 $(u,v)$ 都求出答案。

输入格式

本题有多组数据，第一行是数据组数 $T$。

对于每组数据：第一行两个正整数 $n,m$，分别为 $G$ 的点数和边数。接下来 $m$ 行，每行两个正整数 $x,y$，表示有向图里一条 $x\to y$ 的边。保证没有重边且 $x\lt y$（也就是 $[1,2,\dots,n]$ 总是一个合法拓扑序）。

保证同一个测试点中至多有 $5$ 组数据满足 $n>10$。

输出格式

对每组数据输出一个 $n\times n$ 的矩阵，第 $i$ 行第 $j$ 列是 $v=i,u=j$ 时的答案，注意 $(v,u)$ 的顺序和 $(i,j)$ 是反的。特别地，当 $i=j$ 时请你输出 0。

样例输入输出

样例输入 1

2
3 2
1 2
1 3
4 2
1 2
3 4

样例输出 1

0 0 0
2 0 1
2 1 0
0 0 3 1
6 0 5 3
3 1 0 0
5 3 6 0

样例 1 解释

对于第一组数据，原图共有两种拓扑序 $[1,2,3],[1,3,2]$。满足 $1$ 在 $2$ 前面的有 $2$ 种，所以答案矩阵的第 $2$ 行第 $1$ 列是 $2$；满足 $3$ 在 $2$ 前面的有 $1$ 种，所以答案矩阵的第 $2$ 行第 $3$ 列是 $1$。

样例 2/3

见下发文件。

样例 $2$ 满足子任务 $1$ 的限制。

样例 $3$ 满足子任务 $10$ 的限制。

数据范围

对于所有数据：$1\le T\le 100,1\le n\le 20,0\le m\le \binom n2$，保证同一个测试点中至多有 $5$ 组数据满足 $n>10$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$