Problem Description

You are given a directed graph with $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$.

For each vertex $i$, find out the number of ways to choose exactly $n-1$ edges to form a tree, where all the other $n-1$ vertices can be reached from $i$ through these $n-1$ edges.

Input

The first line contains a single integer $T(1\le T\le 100)$ - the number of test cases.

For each test case:

The first line contains two integers $n,m(1\le n\le 500,0\le m \le n\times (n-1))$ - the number of vertices and the number of edges.

The next $m$ lines, each line contains two integers $x,y(1\le x,y\le n,x\neq y)$, denoting an edge. It is guaranteed that all the edges are different.

It is guaranteed that there are no more than $3$ test cases with $n>100$.

It is guaranteed that there are no more than $12$ test cases with $n>50$.

Output

For each test case, output $n$ integers in a line, the $i$-th integer denotes the answer for vertex $i$. Since the answer may be too large, print it after modulo $10^9+7$.

Please do not have any space at the end of the line.

2
1 0
7 12
1 3
2 1
1 4
5 1
4 7
6 5
2 3
4 6
3 1
6 4
7 1
1 2

1
2 3 1 4 2 6 2