Description 
n<=100000,m<=n+5,k<=100000
Solution
- 由于这题有m<=n+5这个极为特殊的条件，又因为每个端点的影响只跟相邻的点有关，所以我们可以考虑缩小图的规模。
- 我们假设每条边有两个边权，一个是两端点相同颜色时的权s，初始为1，一个是两端点不同时的权t，初始为0，那么一个图的答案就是每条边的边权用对应的权相乘.
- 如果一个点的度数为1，就可以直接把它删掉，并将答案乘上(k-1),注意特判一条链的情况。
- 如果一个点 z 的度数为2，我们可以考虑将这个点的路径给压缩起来，也就是把这个点删掉，再在这个点连向的两个点 x , y 中新加一条边。
- 这条新的边两个端点 x , y 相同颜色时：要么x=z=y，就是s1 * s2;要么
x<>z<>y,就是t1* t2*(k-1)，这个时候z有k-1种选择使得x=y - 这条新的边两个端点 x , y 不同颜色时：要么x<>z<>y,就是t1 * t2*(k-2)；要么x=z<>y或x<>z=y，分别是s1 * t2,t1 * s2
- 缩完图之后，没有度数小于3的点，则3n<=2m,且m<=n+5,所以n<=10,m<=5。状压DP。每一次枚举一个新的集合，代表这个集合里的点都是同样的颜色，那么就与非该集合里的点颜色不同，与同集合里的点颜色相同，乘上对应的边权即可。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100005
#define maxm 600005
#define mo 1000000007
#define ll long long
using namespace std;
int n,m,i,j,x,y,du[maxn],vis[maxn],tot,p[maxn];
int em,e[maxm],nx[maxm],ls[maxn],bz[maxm];
int t,w,d[maxn];
ll k,ans,sum,ec[maxm][2],f[15][1<<11],tota,a[20][4],jc[maxn];
int I(int i){return (i&1)?i+1:i-1;}
void insert(int x,int y,ll ec0,ll ec1){
em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; ec[em][0]=ec0; ec[em][1]=ec1;
em++; e[em]=x; nx[em]=ls[y]; ls[y]=em; ec[em][0]=ec0; ec[em][1]=ec1;
}
ll ksm(ll x,ll y){
ll s=1;
for(;y;y/=2,x=x*x%mo) if (y&1)
s=s*x%mo;
return s;
}
ll C(ll n,ll m){
return jc[n]*ksm(jc[n-m]*jc[m]%mo,mo-2)%mo;
}
void build(){
t=w=0;
for(i=1;i<=n;i++) if (du[i]==1)
d[++w]=i,vis[i]=1;
ans=1;
while (t<w){
x=d[++t];
if (du[x]==0) vis[x]=0;
for(i=ls[x];i;i=nx[i]) if (!bz[i]){
ans=ans*(k-1)%mo;
du[e[i]]--,du[x]--,bz[i]=bz[I(i)]=1;
if (du[e[i]]==1&&!vis[e[i]]) vis[e[i]]=1,d[++w]=e[i];
}
}
t=w=0;
for(i=1;i<=n;i++) if (du[i]==2) d[++w]=i;
while (t<w){
x=d[++t];
int i1=0,i2=0;
for(i=ls[x];i;i=nx[i]) if (!bz[i]) {
if (!i1) i1=i; else i2=i;
}
if (e[i1]==e[i2]) continue;
vis[x]=1;
ll ec0=(ec[i1][0]*ec[i2][0]%mo+ec[i1][1]*ec[i2][1]%mo*1ll*(k-1)%mo)%mo;
ll ec1=(ec[i1][1]*ec[i2][1]%mo*1ll*(k-2)%mo+ec[i1][0]*ec[i2][1]%mo+ec[i1][1]*ec[i2][0]%mo)%mo;
insert(e[i1],e[i2],ec0,ec1);
bz[i1]=bz[I(i1)]=1;
bz[i2]=bz[I(i2)]=1;
}
for(i=1;i<=n;i++) if (!vis[i]) p[i]=++tot;
for(x=1;x<=n;x++) if (!vis[x]){
for(i=ls[x];i;i=nx[i]) if (!bz[i]){
tota++;
a[tota][0]=ec[i][0],a[tota][1]=ec[i][1];
a[tota][2]=p[x],a[tota][3]=p[e[i]];
bz[i]=bz[I(i)]=1;
}
}
}
int _2[15],_3[15],bt[15];
void dp(){
_2[0]=_3[0]=1;
for(i=1;i<=tot;i++) _2[i]=_2[i-1]*2,_3[i]=_3[i-1]*3;
f[0][0]=1,sum=0;
for(i=1;i<=tot;i++){
for(int S=1;S<_3[tot];S++){
int V=0,T=0;
for(j=1;j<=tot;j++) {
bt[j]=S%_3[j]/_3[j-1];
if (bt[j]==1) V+=_2[j-1];
if (bt[j]>=1) T+=_2[j-1];
}
if (!f[i-1][V]||T==V) continue;
ll s=1;
for(j=1;j<=tota;j++) {
x=a[j][2],y=a[j][3];
if (bt[x]==2&&bt[y]==2) s=s*a[j][0]%mo;
if (bt[x]==2&&bt[y]==1||bt[x]==1&&bt[y]==2) s=s*a[j][1]%mo;
}
(f[i][T]+=f[i-1][V]*s%mo)%=mo;
}
(sum+=f[i][_2[tot]-1]*C(k,i)%mo)%=mo;
}
}
int main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
scanf("%d%d%lld",&n,&m,&k);
for(i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
insert(x,y,0,1);
du[x]++,du[y]++;
}
jc[0]=1;
for(i=1;i<=k;i++) jc[i]=1ll*jc[i-1]*i%mo;
build();
dp();
printf("%lld",ans*sum%mo);
}