D - Packing Balls into Boxes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は K 個のボールを N 個の箱に分配しようとしています。箱には左から順に箱 1, 箱 2, \ldots, 箱 N と番号が振られており、ボールにもボール 1, ボール 2, \ldots, ボール K と番号が振られています。箱どうし、ボールどうしはそれぞれ区別されます。

分配には以下のルールがあります：

  1. すべてのボールをいずれかの箱に入れなければならず、各ボールは ちょうど 1 つの箱 に入れられる。
  2. 各箱には 1 個以上 のボールを入れなければならない（空の箱があってはならない）。
  3. さらに、M 個の制約条件が与えられる。j 番目 (1 \leq j \leq M) の制約条件は「ボール U_j とボール V_j は 同じ箱に 入れなければならない」というものである。

ルール 3 の制約条件において、同じ箱に入れなければならない関係は推移的に適用されます。すなわち、ボール A とボール B が同じ箱に入る制約があり、ボール B とボール C が同じ箱に入る制約がある場合、ボール A, B, C はすべて同じ箱に入れなければなりません。一般に、制約条件を繰り返し適用することで同じ箱に入ると導かれるボールの組は、すべて同じ箱に入れる必要があります。

ルール 1, 2, 3 をすべて満たすような分配方法の総数を、998244353 で割った余りを求めてください。なお、条件を満たす分配方法が存在しない場合は 0 を出力してください。

ここで、2 つの分配方法が異なるとは、あるボールが存在して、そのボールが入っている箱の番号が一方の分配方法ともう一方の分配方法で異なることを言います。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq U_j < V_j \leq K (1 \leq j \leq M)
  • (U_j, V_j) の組はすべて異なる。
  • 入力はすべて整数である。

入力

N K M
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、箱の数を表す整数 N、ボールの数を表す整数 K、制約条件の数を表す整数 M が、スペース区切りで与えられる。
  • 続く M 行のうち j 行目 (1 \leq j \leq M) には、j 番目の制約条件におけるボールの番号 U_j と V_j がスペース区切りで与えられる。M = 0 のとき、この部分は存在しない。

出力

分配方法の総数を 998244353 で割った余りを 1 行で出力せよ。

入力例 1

2 4 1
1 2

出力例 1

6

入力例 2

3 2 0

出力例 2

0

入力例 3

5 10 6
1 2
2 3
4 5
6 7
7 8
1 3

出力例 3

120

入力例 4

8 25 18
1 2
2 3
3 4
1 4
5 6
6 7
8 9
10 11
11 12
12 13
13 14
15 16
17 18
18 19
20 21
22 23
23 24
24 25

出力例 4

40320

入力例 5

1 1 0

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is trying to distribute K balls into N boxes. The boxes are numbered Box 1, Box 2, \ldots, Box N from left to right, and the balls are numbered Ball 1, Ball 2, \ldots, Ball K. The boxes are distinguishable from each other, and the balls are distinguishable from each other.

The distribution must follow these rules:

  1. Every ball must be placed in exactly one box, and each ball is placed in exactly one box.
  2. Each box must contain at least one ball (no box may be empty).
  3. Additionally, M constraints are given. The j-th constraint (1 \leq j \leq M) states that "Ball U_j and Ball V_j must be placed in the same box."

In the constraints of Rule 3, the "must be in the same box" relationship is applied transitively. That is, if there is a constraint that Ball A and Ball B must be in the same box, and a constraint that Ball B and Ball C must be in the same box, then Balls A, B, and C must all be placed in the same box. In general, any set of balls that can be derived to be in the same box by repeatedly applying the constraints must all be placed in the same box.

Find the total number of distribution methods that satisfy all of Rules 1, 2, and 3, modulo 998244353. If no valid distribution exists, output 0.

Here, two distribution methods are considered different if there exists a ball that is placed in a box with a different number in one distribution method compared to the other.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq U_j < V_j \leq K (1 \leq j \leq M)
  • All pairs (U_j, V_j) are distinct.
  • All input values are integers.

Input

N K M
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains three space-separated integers: N representing the number of boxes, K representing the number of balls, and M representing the number of constraints.
  • The following M lines each contain the j-th constraint (1 \leq j \leq M): the ball numbers U_j and V_j separated by a space. When M = 0, this part does not exist.

Output

Output the total number of distribution methods modulo 998244353 in a single line.

Sample Input 1

2 4 1
1 2

Sample Output 1

6

Sample Input 2

3 2 0

Sample Output 2

0

Sample Input 3

5 10 6
1 2
2 3
4 5
6 7
7 8
1 3

Sample Output 3

120

Sample Input 4

8 25 18
1 2
2 3
3 4
1 4
5 6
6 7
8 9
10 11
11 12
12 13
13 14
15 16
17 18
18 19
20 21
22 23
23 24
24 25

Sample Output 4

40320

Sample Input 5

1 1 0

Sample Output 5

1