G - グランド・グラフ (Grand Graph) Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 100

リジャッジをしました。(18/12/24 16:07 JST)

問題文

パ研合宿の運営リーダーである E869120 氏は、N 頂点 M 辺の連結な無向グラフを持っています。i 番目の辺は、頂点 a_ib_i を結んでいます。

1224 日、今日はクリスマスイブです。
そのため、彼はグラフに色を付け、パ研部長である reiji1112 氏にプレゼントすることを計画しました。
しかし、辺で直接隣り合う頂点が同じ色だと見栄えが良くないので、辺で直接隣り合う頂点同士は違う色で塗る必要があります。

色は K 色準備されています。色 1, 2, 3, ..., K と番号付けられています。
さて、塗り方は何通りあるでしょうか? 1 \ 000 \ 000 \ 007 で割った余りを求めてください。

制約

  • N1 以上 100 \ 000 以下の整数
  • M1 以上 100 \ 003 以下の整数
  • M - N 3 以下である。
  • K1 以上 1 \ 000 \ 000 \ 000 以下の整数
  • a_i, b_i1 以上 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 の制約は満たしませんが、小課題 28 の制約は満たします。


入力例 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 で割った余りを求めてください。