TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5431
  • Problem
  • P5431图上色
    Limits : Time Limit : 5000 MS   Memory Limit : - KB
    Judgment Tips : 1s,512m
    Description

    何老板给你一个简单无向图(无重边)。图中有$n$个点,$m$条边。点编号 \(1...n\)。一开始,图中的边都没有被涂色。
    何老板有$k$种颜色的油漆。他打算给图中所有边涂色。
    如果一个简单环(该环不会重复经过某个点),设环上有$t$条边,按环的顺序依次编号为 \(e_1,e_2,...,e_t\) 。 何老板可以进行轮换涂色操作,即用原$e_1$的颜色去涂$e_2$,用原$e_2$的颜色去涂$e_3$,...,用原$e_t$的颜色去涂$e_1$。如下图所示:

    如果一种涂色方案$A$通过轮换涂色操作能转换为另一种涂色方案$B$,何老板认为这两种方案本质是相同的。

    何老板想知道,总共有多少种本质不同的涂色方案,答案 mod (10^9+7)

    Input Format

    第一行三个正整数N M K
    接下来M行每行两个正整数ai,bi表示图中的一条边。

    Output Format

    输出一行一个非负整数表示答案。

    Sample Input 1

    4 4 2
    1 2
    2 3
    3 1
    3 4

    Sample Output 1

    8

    Sample Input 2

    5 2 3
    1 2
    4 5

    Sample Output 2

    9

    Sample Input 3

    11 12 48
    3 1
    8 2
    4 9
    5 4
    1 6
    2 9
    8 3
    10 8
    4 10
    8 6
    11 7
    1 8

    Sample Output 3

    569519295

    Hint

    $1≦N≦50$
    $1≦M≦100$
    $1≦K≦100$
    $1≦ai,bi≦N(1≦i≦M)$
    图中没有重边和自环


    Source  ARC062F