给定一个 \(n\) 个点 \(m\) 条边的简单无向图 \(G\)，你需要为每条边染 \(1\) 到 \(k\) 中的一种颜色。
我们定义一次操作为，选择 \(G\) 中的一个简单环，将环上的边进行循环移动。
定义 \(G_1\) 与 \(G_2\) 本质相同，当且仅当 \(G_1\) 能在若干次操作后与 \(G_2\) 相同。
求本质不同的涂色方案数量，对 \(10^9+7\) 取模。
\(1 \leq n \leq 50\)，\(1 \leq m \leq 100\)，\(1 \leq k \leq 100\)。
考虑简单环上循环移动的性质，容易发现如下事实：
- 若两个简单环有公共边，则其内部的边可以任意排列。
我们只需要实现交换两条边即可，你发现其实此时有两个小环和一个大环可以操作，这一步是容易构造方法的，虽然我不会就是了。
接下来我们就可以找到每个点双。
若点双中没有环，每条边都会产生 \(k\) 的贡献。
若点双恰好为一个环，等价于环染色，使用 Pólya 定理即可。
若点双包含 \(\geq 2\) 个环，则两种方案等价当且仅当每种颜色的出现次数相同，我们统计这个组合可以使用插板法。
结束了。
代码大概是东拼西凑的所以有点乱。
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
using namespace std;
const long long mod=1000000007;
vector<int> G[60],dcc[60];
int low[60],dfn[60],seq,tot,root;
bool cut[60];
stack<int> st;
void tarjan(int u){low[u]=dfn[u]=++seq;if(u==root && G[u].empty()){return ;}st.push(u);int child=0;for(int i=0;i<G[u].size();i++){int v=G[u][i];if(!dfn[v]){child++;tarjan(v);low[u]=min(low[u],low[v]);if(low[v]==dfn[u]){if(u!=root || child>1){cut[u]=true;}tot++;while(true){int pre=st.top();st.pop();dcc[tot].push_back(pre);if(pre==v) break;}dcc[tot].push_back(u);}}else{low[u]=min(low[u],dfn[v]);}}
}
long long pow_mod(long long num1,long long num2=mod-2){num1=(num1%mod+mod)%mod;num2=(num2%(mod-1)+(mod-1))%(mod-1);long long num3=1;while(num2){if(num2&1){num3=num3*num1%mod;}num1=num1*num1%mod;num2>>=1;}return num3;
}
bool graph[60][60];
long long fact[210],invfact[210];
long long my_gcd(long long x,long long y){while(y){long long z=x%y;x=y;y=z;}return x;
}
int main(){fact[0]=invfact[0]=1;for(int i=1;i<=200;i++){fact[i]=fact[i-1]*i%mod;invfact[i]=invfact[i-1]*pow_mod(i)%mod;}int n,m;long long k;scanf("%d %d %lld",&n,&m,&k);for(int i=1;i<=m;i++){int u,v;scanf("%d %d",&u,&v);G[u].push_back(v);G[v].push_back(u);graph[u][v]=graph[v][u]=true;}for(int i=1;i<=n;i++){if(!dfn[i]){root=i;tarjan(i);}}long long ans=1;for(int i=1;i<=tot;i++){int cnt_1=0,cnt_2=0;for(int j=0;j<dcc[i].size();j++){cnt_1++;for(int k=j+1;k<dcc[i].size();k++){if(graph[dcc[i][j]][dcc[i][k]]){cnt_2++;}}}if(cnt_1>cnt_2){ans*=k;ans%=mod;}else if(cnt_1==cnt_2){long long pre=0;for(int j=0;j<cnt_1;j++){pre+=pow_mod(k,my_gcd(j,cnt_1));}ans*=pre*pow_mod(cnt_1)%mod;ans%=mod;}else{ans*=fact[cnt_2+k-1]*invfact[cnt_2]%mod*invfact[k-1]%mod;ans%=mod;}}printf("%lld",ans);return 0;
}