给定一个包含 $n$ 个顶点和 $m$ 条边的有向图。顶点编号从 $1$ 到 $n$。

对于每个顶点 $i$，求出选择恰好 $n-1$ 条边构成一棵树的方法数，使得其余 $n-1$ 个顶点都能从 $i$ 出发通过这 $n-1$ 条边到达。

输入格式

第一行包含一个整数 $T(1 \le T \le 100)$，表示测试用例的数量。

对于每个测试用例： 第一行包含两个整数 $n, m(1 \le n \le 500, 0 \le m \le n \times (n - 1))$，分别表示顶点数和边数。 接下来的 $m$ 行，每行包含两个整数 $x, y(1 \le x, y \le n, x \neq y)$，表示一条边。保证所有边各不相同。

保证 $n > 100$ 的测试用例不超过 $3$ 个。 保证 $n > 50$ 的测试用例不超过 $12$ 个。

输出格式

对于每个测试用例，在一行中输出 $n$ 个整数，第 $i$ 个整数表示顶点 $i$ 的答案。由于答案可能很大，请将其对 $10^9 + 7$ 取模后输出。 请确保行末没有多余空格。

样例

输入 1

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

1
2 3 1 4 2 6 2