236 . IOIC 王國
TopCoder
Tags
Description
IOIC 王國是一個獨裁的國家，由帥哥總召 Robert 統治，這個國家一共有 $N$ 座城市以及 $M$ 條道路，每一條道路連接著兩座不同的城市。帥哥總召 Robert 為了監控整個王國，研發了 $K$ 種不同類型的機器人 (每個種類都有無數多個機器人)。他想要將機器人分配到每一條道路上，讓每一條道路都恰有一個機器人監控。
為了增加管理王國的趣味性，總召會進行一些操作，操作的方式如下：總召每次可以選擇一些不同的城市，編號分別為 $x_1, x_2, \ldots, x_t$，使得對所有 $1 \leq i \leq t$，編號 $x_i$ 與 $x_{i + 1}$ 的城市之間都有道路連接，其中 $x_{t + 1} = x_1$。接著，總召會旋轉這些道路上的機器人，也就是說在編號 $x_i$ 與 $x_{i + 1}$ 的城市之間的機器人，會移動到連接著編號 $x_{i + 1}$ 與 $x_{i + 2}$ 的城市之間的道路。
總召很好奇，在這樣的情況下，最多可以選出幾種不同的分配方式，使得對於任意兩種分配方式，都沒有辦法經過若干次操作從一種分配方式變成另一種分配方式？如果存在一條道路在兩種分配方式中被賦予不同種類的機器人，我們就說這兩種分配方式是不同的。
Input Format
輸入的第一行包含三個正整數 $N, M, K$，分別代表城市的數量，道路的數量，以及機器人類型的數量。
接下來的 $M$ 行，每一行都有兩個正整數 $x, y$，代表這條道路連接著第 $x$ 座城市與第 $y$ 座城市。
- $1 \leq N, M \leq 5 \times 10^ 5$
- $1 \leq K \leq 10^ 9$
- $1 \leq x, y \leq N, x \neq y$
- 任意兩座城市之間不會有兩條以上的道路連接
Output Format
請輸出一個整數代表分配的方案數，答案請模 $998244353$ 之後輸出。
Sample Input 1
4 4 2
1 2
2 3
3 1
2 4
1 2
2 3
3 1
2 4
Sample Output 1
8
Sample Input 2
5 6 3
1 2
2 3
3 1
3 4
4 5
3 5
1 2
2 3
3 1
3 4
4 5
3 5
Sample Output 2
121
Sample Input 3
4 5 2
1 2
2 3
3 4
2 4
4 1
1 2
2 3
3 4
2 4
4 1
Sample Output 3
6
Sample Input 4
10 8 4
9 4
5 3
6 4
2 4
6 10
4 7
9 2
4 10
9 4
5 3
6 4
2 4
6 10
4 7
9 2
4 10
Sample Output 4
9216
Hints
Problem Source
IOICamp 2021 Day5 pK
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | 範例測資 | 0 |
| 2 | 0~98 | 無額外限制 | 100 |