위상 정렬

방향 비순환 그래프(DAG)의 위상 정렬은 정점들의 순열 $p_1, \ldots, p_n$으로, 모든 간선에 대해 시작 정점이 도착 정점보다 순열에서 앞에 오는 것이다.

방향 비순환 그래프가 주어진다. 각 정점 쌍 $(u, v)$에 대해, 정점 $u$가 정점 $v$보다 앞에 오는 위상 정렬의 개수를 구하라.

첫 줄에 테스트 케이스의 개수 $t$가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 정점의 개수 $n$과 간선의 개수 $m$이 주어진다($1 \le n \le 20$, $0 \le m \le n(n-1)/2$). 다음 $m$개의 줄에는 정점 $u_i$에서 정점 $v_i$로 가는 간선을 나타내는 두 정수 $u_i$, $v_i$가 주어진다($1 \le u_i < v_i \le n$).

테스트 케이스는 최대 100개이다. 그중 최대 5개의 테스트 케이스에서 $n > 10$이다.

각 테스트 케이스마다 $n$개의 수로 이루어진 $n$개의 줄을 출력한다. $i$번째 줄의 $j$번째 수는 정점 $j$가 정점 $i$보다 앞에 오는 위상 정렬의 개수와 같다. $i = j$이면 0이다.