C - Max Permutation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) のうち、以下の条件を全て満たすものの個数を 998244353 で割ったあまりを出力してください。

  • \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
  • i \neq j ならば (A_i,B_i) \neq (A_j,B_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 個です。

入力例 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

Score: 700 points

Problem Statement

Print the number, modulo 998244353, of permutations P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) that satisfy all of the following conditions:

  • \max(P_{A_i},P_{B_i}) = C_i\ (1 \le i \le M).

Constraints

  • 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.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

Output

Print the answer.

Sample Input 1

4 2
1 2 4
2 3 2

Sample Output 1

2

The two permutations P that satisfy the conditions are (4,1,2,3) and (4,2,1,3).

Sample Input 2

6 3
1 4 3
2 5 6
3 4 2

Sample Output 2

8

Sample Input 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

Sample Output 3

1209600