시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 6 5 5 83.333%

문제

The topological ordering of a directed acyclic graph is a permutation of its vertices p1, . . . , pn 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 such that vertex u comes before vertex v.

입력

The first line contains a single integer t, the number of test cases. Descriptions of t test cases follow.

In the first line of each test case there are two integers n and m: the number of vertices and arcs (1 ≤ n ≤ 20, 0 ≤ m ≤ n · (n − 1)/2).

Each of the next m lines contains two integers ui and vi, denoting the arc from vertex ui to vertex vi (1 ≤ ui < vi ≤ n).

There are at most 100 test cases in the input. In at most 5 test cases n > 10.

출력

For each test case, print n lines of n numbers each. The j-th number in the i-th line should equal the number of topological orderings where vertex j is before vertex i. In particular, it should equal 0 if i = j.

예제 입력 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