← 返回题目列表

AtCoder · pakencamp_2018_day2_g

G. 大图

中文机器翻译题面 查看原题

配点: 100 点

我做了重新判断。 (24 年 12 月 18 日 16:07 日本标准时间)

問題文

PA训练营管理负责人 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 求余数。