T394091 寒冬

冬天到了，小明家里的树不但没有枯萎，反倒越来越繁茂……

你有一个 $ n $ 个点 $ m $ 条边的无向图，现在你要为每个节点染上一个编号在 $ [1,k] $ 之间的颜色，需要保证每条边连接的两个顶点的颜色不能相同。你想知道一共有多少种不同的染色方案。答案对 $ 10^9+7 $ 取模。 两种染色方案不同当且仅当至少一个节点在两种方案中被染上了不同的颜色。

第一行三个整数 $n,m,k$，表示顶点数，边数，颜色数。 接下来 $ m $ 行，每行两个整数 $ x_i,y_i $，表示一条连接 $ x_i $ 和 $ y_i $ 的无向边。

输出一行一个整数，表示总方案数。答案对 $ 10^9+7 $ 取模。

对于所有数据，保证 $2\le n \le 10^5,n-1\le m\le n+3,1\le k \le 10^9,1\le x_i\le y_i\le n$，保证图连通，无自环，无重边。 **请注意 $\bm m$ 特殊的数据范围。** | 子任务编号 | 分数 | $n\le$ | $m=$ | $k\le$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1 $ | $ 5 $ | $ 8 $ | | $ 3 $ | | $ 2 $ | $ 10 $ | $ 8 $ | | | | $ 3 $ | $ 14 $ | | $ n-1 $ | | | $4 $| $8 $| |$ n $| | | $5$ | $16$ | |$ n+1$ | | |$6$|$21$||$n+2$|| |$7$|$19$|$10^3$|$n+3$|$10^3$| |$8$|$7$||$n+3$|| 空白为无特殊要求。 本题不卡常，时限为 std 的 $20$ 倍。