配点: 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 求余数。