Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 100 点
リジャッジをしました。(18/12/24 16:07 JST)
問題文
パ研合宿の運営リーダーである E869120 氏は、N 頂点 M 辺の連結な無向グラフを持っています。i 番目の辺は、頂点 a_i と b_i を結んでいます。
12 月 24 日、今日はクリスマスイブです。
そのため、彼はグラフに色を付け、パ研部長である reiji1112 氏にプレゼントすることを計画しました。
しかし、辺で直接隣り合う頂点が同じ色だと見栄えが良くないので、辺で直接隣り合う頂点同士は違う色で塗る必要があります。
色は K 色準備されています。色 1, 2, 3, ..., K と番号付けられています。
さて、塗り方は何通りあるでしょうか? 1 \ 000 \ 000 \ 007 で割った余りを求めてください。
制約
- N は 1 以上 100 \ 000 以下の整数
- M は 1 以上 100 \ 003 以下の整数
- M - N は 3 以下である。
- K は 1 以上 1 \ 000 \ 000 \ 000 以下の整数
- a_i, b_i は 1 以上 N 以下の整数
- a_i < b_i (1 \leq i \leq M)
- (a_i, b_i) \neq (a_j, b_j) (i \neq j)
入力
入力は以下の形式で標準入力から与えられます。
N M K a_1 b_1 a_2 b_2 a_3 b_3 ... a_M b_M
出力
グラフの塗り方は何通りあるか、1 \ 000 \ 000 \ 007 で割った余りを求めてください。
小課題
小課題 1 [4 点]
入力は以下の条件を満たす。
- N \leq 8.
- K \leq 2.
小課題 2 [13 点]
- N \leq 8 を満たす。
小課題 3 [8 点]
- M - N = -1 かつ a_i = i, b_i = i + 1 (1 \leq i \leq M) を満たす。
小課題 4 [13 点]
- M - N \leq -1 を満たす。
小課題 5 [13 点]
- M - N \leq 0 を満たす。
小課題 6 [13 点]
- M - N \leq 1 を満たす。
小課題 7 [13 点]
- M - N \leq 2 を満たす。
小課題 8 [23 点]
- 追加の制約はない。
入力例 1
3 2 2 1 2 2 3
出力例 1
2
以下の 2 通りの塗り方が条件を満たします。
入力例 2
3 2 5 1 2 2 3
出力例 2
80
この入力例は小課題 1 の制約は満たしませんが、小課題 2 〜 8 の制約は満たします。
入力例 3
4 3 1 1 2 2 3 2 4
出力例 3
0
入力例 4
6 5 4 1 2 1 3 2 4 2 5 3 6
出力例 4
972
入力例 5
10 10 100 1 2 1 3 2 4 2 5 2 6 2 7 3 8 5 9 9 10 4 8
出力例 5
332858118
答えを 1 \ 000 \ 000 \ 007 で割った余りを求めてください。