rt，上一场cf的div1C/div2E，用了一种并查集找环的方式，简单的来说就是在同一个并查集内的元素只会被当作一个元素合并，当时觉得是 $\log ^2$ 的（确实跑过去了），后面想了想总感觉有些奇怪。提交记录

code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5,M=998244353;
#define int ll
/*
偶环全相等 奇环全是0
*/
int T,n,m,V;
struct edge{int to,nxt;}es[N<<1];
int ecnt,head[N];
void addedge(int u,int v){es[++ecnt].nxt=head[u];es[ecnt].to=v;head[u]=ecnt;}
int w[N],bcj[N];
int find(int x){
    if(bcj[x]==x)return x;
    return bcj[x]=find(bcj[x]);
}
int mark[N];
void merge(int x,int y){
    //cout<<x<<":::"<<y<<endl;
    int fx=find(x),fy=find(y);
    if(mark[fx]||mark[fy])mark[fx]=mark[fy]=1;
    bcj[fx]=fy;
}
bool vis[N];int st[N][22];
int dep[N];
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--)if(dep[st[x][i]]>=dep[y])x=st[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--){
        if(st[x][i]!=st[y][i]){
            x=st[x][i];
            y=st[y][i];
        }
    }
    return st[x][0];
}
int lst[N];//上一个没有被压缩的节点

void dfs(int now,int fa){
    st[now][0]=fa;dep[now]=dep[fa]+1;lst[now]=fa;
    vis[now]=1;
    for(int i=1;i<=20;i++){
        st[now][i]=st[st[now][i-1]][i-1];
    }
    for(int i=head[now];i;i=es[i].nxt){
        if(es[i].to==fa)continue;
        if(vis[es[i].to]){
            int tl=lca(now,es[i].to);
            //cout<<now<<" "<<es[i].to<<" "<<tl<<endl;
            if((dep[now]-dep[tl]+dep[es[i].to]-dep[tl]+1)%2==1)mark[find(now)]=1;
            for(int j=now,prev=0;dep[j]>dep[tl];j=lst[j]){
                if(prev and dep[lst[tl]]<dep[lst[prev]])lst[prev]=lst[tl];
                //cout<<j<<"?"<<lst[j]<<endl;
                if(dep[lst[j]]>=dep[tl])merge(j,lst[j]);
                prev=j;
            }
            for(int j=es[i].to,prev=0;dep[j]>dep[tl];j=lst[j]){
                if(prev and dep[lst[tl]]<dep[lst[prev]])lst[prev]=lst[tl];
                //cout<<j<<"?"<<lst[j]<<endl;
                if(dep[lst[j]]>=dep[tl])merge(j,lst[j]);
                prev=j;
            }
            merge(now,tl);
            merge(es[i].to,tl);
        }
        else dfs(es[i].to,now);
    }
}int ttmp[N];
signed main(){
    cin>>T;
    while(T--){
        for(int i=1;i<=n;i++){
            w[i]=lst[i]=mark[i]=vis[i]=head[i]=dep[i]=0;
            
            for(int j=0;j<=20;j++)st[i][j]=0;
        }ecnt=0;
        cin>>n>>m>>V;
        for(int i=1;i<=n;i++)bcj[i]=i,ttmp[i]=-1;
        for(int i=1;i<=n;i++)cin>>w[i];
        int u,v;
        for(int i=1;i<=m;i++){
            cin>>u>>v;
            addedge(u,v);
            addedge(v,u);
        }
        dfs(1,0);
        int ans=1;
        for(int i=1;i<=n;i++){
            // cout<<find(i)<<" "<<mark[find(i)]<<endl;
            if(mark[find(i)] and (w[i]!=0 and w[i]!=-1))ans=0;
            else if(!mark[find(i)] and ttmp[find(i)]==-1)ttmp[find(i)]=w[i];
            else if(!mark[find(i)] and w[i]!=-1 and ttmp[find(i)]!=w[i])ans=0;
        }
        for(int i=1;i<=n;i++){
            if(!mark[find(i)] and ttmp[i]==-1 and find(i)==i)ans*=V;ans%=M;
        }
        cout<<ans<<endl;
    }
    return 0;
}