分数: 700 点
问题陈述
打印数字,模数 998244353,排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) 满足以下所有条件:
- \max(P_{A_i},P_{B_i}) = C_i\ (1 \le i \le M).
约束
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- 1 \le A_i < B_i \le N
- 1 \le C_i \le N
- (A_i,B_i) \neq (A_j,B_j) if i \neq j.
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
输出
打印答案。
示例输入 1
4 2 1 2 4 2 3 2
示例输出 1
2
两种排列 P 满足条件的是 (4,1,2,3) 和 (4,2,1,3).
示例输入 2
6 3 1 4 3 2 5 6 3 4 2
示例输出 2
8
示例输入 3
20 17 9 16 13 5 14 20 15 20 14 5 13 17 18 20 14 14 20 20 6 13 11 12 16 19 2 15 10 6 17 11 7 18 7 8 18 12 8 16 13 6 16 13 2 18 10 9 10 15 7 14 20
示例输出 3
1209600