Topological Ordering

The topological ordering of a directed acyclic graph is a permutation of its vertices $p_1, \ldots, p_n$ such that, for each arc, its source comes before its target in the permutation.

You are given a directed acyclic graph. For each pair of vertices $(u, v)$, count the number of topological orderings in which vertex $u$ comes before vertex $v$.

The first line contains a single integer $t$, the number of test cases. Each test case follows.

The first line of each test case contains two integers $n$ and $m$, the number of vertices and arcs ($1 \le n \le 20$, $0 \le m \le n(n-1)/2$). Each of the next $m$ lines contains two integers $u_i$ and $v_i$, denoting an arc from vertex $u_i$ to vertex $v_i$ ($1 \le u_i < v_i \le n$).

There are at most 100 test cases. In at most 5 of them, $n > 10$.

For each test case, print $n$ lines of $n$ numbers each. The $j$-th number in the $i$-th line equals the number of topological orderings in which vertex $j$ comes before vertex $i$. When $i = j$, the number is 0.