← 返回题目列表

AtCoder · arc176_c

C. 最大排列

中文机器翻译题面 查看原题

分数: 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