题目分析：
如果一个双连通分量是简单环，那么用polya原理计数循环移位即可。
如果一个双连通分量不是简单环，那么它必然可以两两互换，不信你可以证明一下相邻的可以互换。
如果一条边是桥，那么直接乘以k就行了。
代码：
#include<bits/stdc++.h>
using namespace std; const int mod = ;
const int maxn = ; int n,m,k;
vector <int> g[maxn]; int fa[maxn],arr[maxn],dfn[maxn],bccnum,low[maxn],cl; vector <pair<int,int> > bcc[maxn];
vector <int> hhh[maxn]; void read(){
scanf("%d%d%d",&n,&m,&k);
for(register int i=;i<=m;i++){
int u,v; scanf("%d%d",&u,&v);
g[u].push_back(v); g[v].push_back(u);
}
} stack<int> sta;
void Tarjan(int now,int f){
fa[now] = f;
low[now] = dfn[now] = ++cl;
sta.push(now);
for(int i=;i<g[now].size();i++){
if(g[now][i] == f) continue;
if(dfn[g[now][i]] > dfn[now]) continue;
if(!dfn[g[now][i]]){
Tarjan(g[now][i],now);
low[now] = min(low[now],low[g[now][i]]);
}else{
low[now] = min(low[now],dfn[g[now][i]]);
hhh[now].push_back(g[now][i]);
}
}
if(f == || low[now] >= dfn[fa[now]]){
bccnum++;
while(true){
int k = sta.top();sta.pop();
arr[k] = ;
if(fa[k] == ) break;
bcc[bccnum].push_back(make_pair(k,fa[k]));
for(int i=;i<hhh[k].size();i++){
bcc[bccnum].push_back(make_pair(k,hhh[k][i]));
}
if(k == now) break;
}
if(bcc[bccnum].size() == ) bccnum--;
}
} int C[maxn*][maxn*]; int fast_pow(int now,int pw){
int ans = ,dt = now, bit = ;
while(bit <= pw){
if(bit & pw){ans =1ll*ans*dt%mod;}
dt = 1ll*dt*dt%mod; bit<<=;
}
return ans;
} int solve(int now){
int ans = ;
for(register int i=;i<=now;i++){
ans += fast_pow(k,__gcd(now,i));
ans %= mod;
}
ans = 1ll*ans*fast_pow(now,mod-)%mod;
return ans;
} int hap[maxn];
void work(){
for(register int i=;i<=n;i++){
if(arr[i]) continue;
Tarjan(i,);
}
C[][] = ;
for(register int i=;i<=;i++){
C[i][] = C[i][i] = ;
for(register int j=;j<i;j++){
C[i][j] = (C[i-][j] + C[i-][j-])%mod;
}
}
int ans = ;
for(register int i=;i<=bccnum;i++){
int flag = ;
for(register int j=;j<bcc[i].size();j++){
if(hap[bcc[i][j].first] && hap[bcc[i][j].second]) flag--;
hap[bcc[i][j].first]++; hap[bcc[i][j].second]++;
}
for(register int j=;j<bcc[i].size();j++){
hap[bcc[i][j].first]--; hap[bcc[i][j].second]--;
}
if(flag == || flag == ){
if(bcc[i].size() == ) ans = 1ll*ans*k%mod;
else ans = 1ll*ans*solve(bcc[i].size())%mod;
}else{
ans = 1ll*ans*C[bcc[i].size()+k-][k-]%mod;
}
}
printf("%d",ans);
} int main(){
read();
work();
return ;
}