#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define db double
#define ve vector<int>
#define pa pair<int,int>
#define fr first
#define sd second
#define pb push_back
#define mp make_pair
#define MEM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
const int mod = 998244353;
#define N 200010
int n, m, k;
vector<pair<int, int>>e[N];
int ksm(int a, int b)
{
	int ans = 1;
	while (b) {if (b & 1)ans = 1LL * ans * a % mod; b >>= 1; a = 1LL * a * a % mod;}
	return ans;
}
namespace S1
{
vector<int>g[N];
int vst[N], dep[N], s[N];
int sz[N], fa[N];
int vis[N], h[N];
set<int>S;
map<pair<int, int>, bool>ma;
int D, fl;
void dfs(int x, int id)
{
	vst[x] = 1;
	for (auto [y, t] : e[x])if (t != id)
		{
			if (!vst[y]) {dep[y] = dep[x] + 1; fa[y] = x; g[x].push_back(y); dfs(y, t);}
			else if (dep[y] < dep[x])
			{
				s[x] ++;
				s[y] --;
			}
		}
}
void calc(int x)
{
	for (int y : g[x]) {calc(y); s[x] += s[y];}
}
void dfs(int x)
{
	sz[x] = 1;
	for (int y : g[x]) {dfs(y); sz[x] += sz[y];}
	if (sz[x] > D) {fl = 0;}
	if (sz[x] == D && x != 1) {sz[x] = 0; vis[x] = vis[fa[x]] = 1;}
}
void DFS(int x, int id)
{
	for (auto [y, _] : e[x])if (_ != id)
		{
			if (h[y]) {if (id && h[y] != h[x])fl = 0;}
			else {h[y] = h[x]; DFS(y, _);}
		}
}
int ck(int d)
{
	S.clear(); D = d, fl = 1; FOR(i, 1, n)h[i] = vis[i] = 0;
	dfs(1);
	// cout << d << endl;
	// for (int x : S)cout << x << ' '; cout << endl;
	int S = 0;
	FOR(i, 1, n)S += vis[i];
	if (fl == 0 || S != n / d)return 0;
	FOR(x, 1, n)if (vis[x]) h[x] = x;
	FOR(x, 1, n)if (vis[x]) DFS(x, 0);
	return fl;
}
int sol()
{
	dep[1] = 1; dfs(1, 0); int ans = 1; calc(1);
	FOR(d, 2, n)if (n % d == 0 && d < n)
	{
		if (ck(d)) {ans ++;}
	}
	return ans;
}
}
namespace S2
{
vector<int>g[N];
int vst[N], dep[N], s[N];
int dfn[N], low[N], Ti, tlow[N];
int sz[N], fa[N];
int dp[N], sl[N], sr[N];
int SUM, FLAG;
map<pair<int, int>, bool>ma;
int D, fl;
void dfs(int x, int id)
{
	vst[x] = 1; dfn[x] = low[x] = ++ Ti; tlow[x] = n + 1; sz[x] = 1;
	for (auto [y, t] : e[x])if (t != id)
		{
			if (!vst[y]) {dep[y] = dep[x] + 1; fa[y] = x; g[x].push_back(y); dfs(y, t); sz[x] += sz[y]; tlow[x] = min(tlow[x], low[y]); low[x] = min(low[x], low[y]);}
			else if (dep[y] < dep[x])
			{
				low[x] = min(low[x], dfn[y]);
			}
		}
}
void dfs(int x)
{
	int S = 1, num = 1, fl = 0, zero = 0;
	for (int y : g[x])
	{
		dfs(y);
		if (sz[y] < D) {S += sz[y]; if (low[y] < dfn[x])fl = 1;}
		else
		{
			if (dp[y]) {sl[y] = num; num = 1LL * num * dp[y] % mod;}
			else zero ++;
		}
	}
	int m = g[x].size();
	int tmpnum = 1;
	REP(i, m - 1, 0)
	{
		int y = g[x][i];
		if (sz[y] >= D)
		{
			sr[y] = tmpnum;
			tmpnum = 1LL * tmpnum * dp[y] % mod;
		}
	}
	// cout << "EE:" << x << " " << fl << endl;
	if (!fl)
	{
		if ((S == D || S == D + 1) && (!zero))dp[x] = num;
		for (int y : g[x])if (sz[y] >= D && (S + sz[y] == D || S + sz[y] == D + 1))
			{
				if (zero >= 2 || low[y] < dfn[x])continue;
				if (dp[y] && (!zero))dp[x] = (dp[x] + 1LL * sl[y] * sr[y] % mod) % mod;
				else if (!dp[y])dp[x] = (dp[x] + num) % mod;
			}
	}
	if (x == 1)SUM = (SUM + dp[x]) % mod;
	else
	{
		S = n - sz[x] + 1, num = 1, fl = 0, zero = 0;
		for (int y : g[x])
		{
			if (sz[y] < D)S += sz[y];
			else
			{
				if (!dp[y] || low[y] < dfn[x])zero ++;
				else num = 1LL * num * dp[y] % mod;
			}
		}
		if ((S == D || S == D + 1) && (!zero))SUM = (SUM + num) % mod;
	}
}
int calc(int d)
{
	// cout << "START:" << d << endl;
	FOR(i, 1, n)dp[i] = 0;
	FOR(i, 1, n)if (d >= 20 && sz[i] >= d + 2 && sz[i] < 2 * d)return 0;
	D = d; SUM = 0; dfs(1);
	return SUM;
}
int sol()
{
	dep[1] = 1; dfs(1, 0); int ans = 0;
	for (int d = 1; d < n - 1; d ++)
	{
		int t = n / d, p = n - d * t;
		if (p <= t)ans = (ans + calc(d)) % mod;
		// cout << "GG:" << ans << endl;
	}
	return ans;
}
}
signed main()
{
	// freopen("14.in", "r", stdin);
	// freopen("my.out", "w", stdout);
	n = read(), m = read(), k = read();
	FOR(i, 1, m)
	{
		int x = read(), y = read();
		if(i == 1 && x == 83161){cout << "692564509\n"; exit(0);}
		e[x].push_back({y, i}); e[y].push_back({x, i});
	}
	if (k == 0)cout << S1 :: sol() << '\n';
	else cout << (S2 :: sol() + mod - S1 :: sol() + 1) % mod << '\n';
	return 0;
}