#include<bits/stdc++.h>
#define LL long long
#define MOD 998244353
using namespace std;

LL n,m,k,u,v,pos,ans=1,tmp,numa,numb;
LL head[200005],f[200005],s1[200005];
bool vis[200005];

struct Edge
{
	LL u,v,nxt;
}e[400005];

void addEdge(LL u,LL v)
{
	e[++pos]={u,v,head[u]};
	head[u]=pos;
}

void init()
{
	for(LL i=1;i<=n;i++)
		f[i]=i,s1[i]=1;
}

LL find(LL x)
{
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}

bool Judge(LL a,LL b)
{
	return find(a)==find(b);
}

void Merge(LL a,LL b)
{
	if(Judge(a,b)) return ;
	s1[find(b)]+=s1[find(a)];
	f[find(a)]=f[find(b)];
}

LL qpow(LL x,LL y)
{
	if(y==1) return x%MOD;
	if(y==0) return 1%MOD;
	LL res=qpow(x,y/2)%MOD;
	res*=res;
	res%=MOD;
	if(y&1) res*=x;
	res%=MOD;
	return res%MOD;
}

void DFS(LL st){
	for(LL i=head[st];i;i=e[i].nxt){
		LL v=e[i].v;
		if(!vis[v]) vis[v]=true,DFS(v);
	}
}

void check(LL st)
{
	DFS(st);
	if(head[st]==0){ans=ans*k%MOD;return;}
	LL tota=find(st),totb=find(e[head[st]].v);
	if(tota==totb) printf("0"),exit(0);
	LL p1=s1[tota],p2=s1[totb];
	LL res=(qpow(numa,p1)*qpow(numb,p2))%MOD+(qpow(numb,p1)*qpow(numa,p2))%MOD;
	ans*=res;
	ans%=MOD;
}

int main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	init();
	for(LL i=1;i<=m;i++){
		scanf("%lld%lld",&u,&v);
		addEdge(u,v);
		addEdge(v,u);
	}
	for(LL u=1;u<=n;u++)
		for(LL i=head[u];e[i].nxt;i=e[i].nxt)
			Merge(e[i].v,e[e[i].nxt].v);
	for(LL i=1;i<=n;i++)
		if(!vis[find(i)]) tmp++,vis[find(i)]=true;
	memset(vis,false,sizeof vis);
	numa=k/2,numb=k-numa;
	for(LL i=1;i<=n;i++)
		if(!vis[i]) vis[i]=true,check(i);
	printf("%lld",ans);
}