$\hspace{15pt}$在平行时空的上一次循环里，小$L$同学并没有成功进入 International Counting Path Competition (ICPC) World Finals.

$\hspace{15pt}$这一世，他又转生归来，来到了新的轮回.

$\hspace{15pt}$并且，他觉醒了新的转生系统，他知道，前往 ICPCWF 的路径和节点会形成一个 DAG（如果你不知道 DAG 是什么的话，不告诉你），并且这个 DAG 是已知的！

$\hspace{15pt}$他想知道，从任何一个节点开始，能够成功进入 ICPCWF 的晋级路线有多少条.

$\hspace{15pt}$请你帮他算算！

$\hspace{15pt}$给你一个有 $N$ 个节点，$M$ 条边的简单有向图，节点编号从 $1$ 到 $N$，第 $i$ 条边链接从 $u_i$ 到 $v_i$，保证图内无环.

$\hspace{15pt}$找到对于 $1 \leq K \leq N-1$，每一个 $K$ 到 $N$ 的路径数目，结果对于 $998244353$ 取模.

$\hspace{15pt}$给你 $T$ 组测试点，请你顺序解决每一个.

Constraints

• $1\leq T\leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq min(\frac{N(N-1)}{2}, 2 \times 10 ^ 5)$
• $1 \leq u_i \leq N$
• $1 \leq v_i \leq N$
• 如果 $i \neq j$，那么 $(u_i, v_i) \neq (u_j, v_j)$
• 给出的图是一个简单有向无环图
• $N$ 的和不超过 $2 \times 10^5$
• $M$ 的和不超过 $2 \times 10^5$
• 给定的数字均为非负整数

Input

$\hspace{15pt}$通过标准输入输入数据，满足以下格式：

$T \\ case_1\\ case_2\\ .\\ .\\ case_T\\$

$\hspace{15pt}$每一组测试用例满足以下格式：

$N\ M \\ u_1\ v_1\\ u_2\ v_2\\ .\\ .\\ u_M\ v_M\\$

Output

$\hspace{15pt}$输出共T行，对于第 $i$ 行，你要输出 $i$ 组测试用例的答案.

$\hspace{15pt}$对于每一个测试用例，你要输出 $N - 1$ 个数字，空格分割，表示 $1\leq K \leq N-1$ 的答案，对 $998244353$ 取模.

Samples

1
6 5
1 4
3 4
4 5
5 2
2 6

1 1 1 1 1

1
6 7
1 4
3 4
4 5
5 2
2 6
4 6
3 2

2 1 3 2 1