题解

1.用并查集合并每条允许交换边。

2.按连通分量统计大小和每种字母的次数。

3.预处理阶乘与逆阶乘，计算每个分量的多重集排列数并相乘，得到 $W$。

4.检查是否有某个分量内部出现重复字符。有则输出$W$，否则输出 $W/2$。

/*
如果一个字符串中，每个字母不重复
那么奇数次交换和偶数次交换的排列一定不一样
奇数次交换和偶数次交换是一样的

引理1：
冒泡排序的交换次数=逆序对个数
因为每次都是相邻交换，后面较小值一定会和前面较大值交换
且一定不会和前面较小值交换

引理2：
大小为n全排列的

*/
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=2e5+5;
int n,m;
string s;

int f[N];//并查集的父节点
int sz[N];//并查集启发式合并

//并查集
int find(int x){
    if(f[x]==x)return x;
    return f[x]=find(f[x]);
}
void unite(int x,int y){
    int rx=find(x),ry=find(y);
    if(rx!=ry){
        if(sz[rx]>sz[ry])f[ry]=rx,sz[rx]+=sz[ry];
        else f[rx]=ry,sz[ry]+=sz[rx];
    }
}

//预处理阶乘和阶乘的逆元
vector<ll>invfac(1,1);
vector<ll>fac(1,1);
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b%2==1)ans*=a;
        ans%=mod;
        a=a*a%mod;
        b/=2;
    }
    return ans%mod;
}
void init(){
    fac.resize(n+1);
    invfac.resize(n+1);
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%mod;
    invfac[n]=qpow(fac[n],mod-2);
    for(int i=n;i>1;i--)
        invfac[i-1]=invfac[i]*i%mod;
}
int main(){
    cin>>n>>m>>s;
    s=" "+s;
    init();
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        unite(a,b);
    }
    vector<vector<char>>have(n+1);
    for(int i=1;i<=n;i++)
        have[find(i)].push_back(s[i]);
    ll ans=1;
    bool f=0;
    for(int i=1;i<=n;i++){
        if(have[i].size()>1){
            vector<ll>cnt(26,0);//记录每个字母出现次数
            ll tot=0;
            ll flag=0;
            for(auto c:have[i]){
                cnt[c-'a']++;
                tot++;
            }
            ll now=1;
            now=now*fac[tot]%mod;
            for(int i=0;i<26;i++){
                if(cnt[i]>0)now=now*invfac[cnt[i]]%mod;
                if(cnt[i]>1)f=1;
            }
            ans=ans*now%mod;
        }
    }
    if(!f){
        ans=ans*invfac[2]%mod;
    }
    cout<<ans%mod;
    return 0;
}