#P13858. [pakencamp2018 day2]Grand Graph

    ID: 13059 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200图论动态规划枚举数学组合数学DFS

[pakencamp2018 day2]Grand Graph

题目描述

作为パ研合宿的组织负责人,E869120E869120 先生拥有一个由 NN 个顶点和 MM 条边组成的连通无向图。在这个图中,第 ii 条边连接顶点 aia_i 和 bib_i。

今天是 1212 月 2424 日,正是圣诞节前夕。因此,他计划给这个图染色,并将其作为礼物送给パ研部长 reiji1112reiji1112。不过,为了美观,直接相连的两个顶点不能涂成相同的颜色。

共准备了 KK 种颜色,分别标记为 1,2,3,…,K1, 2, 3, \ldots, K。你需要计算有多少种不同的染色方案。最后,请输出方案数对 1 000 000 0071\ 000\ 000\ 007 取模的结果。

输入格式

输入通过标准输入给出:

NN MM KK a1a_1 b1b_1 a2a_2 b2b_2 a3a_3 b3b_3 ... aMa_M bMb_M

输出格式

请输出符合条件的染色方案数,并对 1 000 000 0071\ 000\ 000\ 007 取模。

数据范围

  • 1≤N≤100,0001 \leq N \leq 100,000
  • 1≤M≤100,0031 \leq M \leq 100,003
  • M−N≤3M - N \leq 3
  • 1≤K≤1,000,000,0001 \leq K \leq 1,000,000,000
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • ai<bia_i < b_i(1≤i≤M1 \leq i \leq M)
  • (ai,bi)≠(aj,bj)(a_i, b_i) \neq (a_j, b_j) 当 i≠ji \neq j 时

附加任务

任务 1 [4 分]
输入限制:

  • N≤8N \leq 8
  • K≤2K \leq 2

任务 2 [13 分]

  • N≤8N \leq 8

任务 3 [8 分]

  • 满足 M−N=−1M - N = -1 且 ai=i,bi=i+1a_i = i, b_i = i + 1(1≤i≤M1 \leq i \leq M)

任务 4 [13 分]

  • 满足 M−N≤−1M - N \leq -1

任务 5 [13 分]

  • 满足 M−N≤0M - N \leq 0

任务 6 [13 分]

  • 满足 M−N≤1M - N \leq 1

任务 7 [13 分]

  • 满足 M−N≤2M - N \leq 2

任务 8 [23 分]

  • 没有额外限制

示例解释

第一种示例中,有以下两种符合条件的染色方案:

第二种示例不符合任务 1 的限制条件,但满足任务 2 到任务 8 的限制条件。

在第五种示例中,请确保输出的结果是对 1 000 000 0071\ 000\ 000\ 007 取模的值。

输入输出样例 #1

输入 #1

3 2 2
1 2
2 3

输出 #1

2

输入输出样例 #2

输入 #2

3 2 5
1 2
2 3

输出 #2

80

输入输出样例 #3

输入 #3

4 3 1
1 2
2 3
2 4

输出 #3

0

输入输出样例 #4

输入 #4

6 5 4
1 2
1 3
2 4
2 5
3 6

输出 #4

972

输入输出样例 #5

输入 #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