시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 15 | 13 | 12 | 85.714% |
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.
2 3 2 1 2 1 3 4 2 1 2 3 4
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