TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5431
  • 問題
  • P5431图上色
    制限 : 時間制限 : 5000 MS   メモリ制限 : - KB
    審判説明 : 1s,512m
    問題説明

    何老板给你一个简单无向图(无重边)。图中有$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)

    入力形式

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

    出力形式

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

    サンプル入力 1

    4 4 2
    1 2
    2 3
    3 1
    3 4

    サンプル出力 1

    8

    サンプル入力 2

    5 2 3
    1 2
    4 5

    サンプル出力 2

    9

    サンプル入力 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

    サンプル出力 3

    569519295

    ヒント

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


    ソース  ARC062F