#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b >>= 1, a *= a) {
        if (b & 1)
            res *= a;
    }
    return res;
}
template<const i64 P>
class ModInt {
public:
    i64 x;
    static i64 Mod;

    ModInt() : x{0} {}
    ModInt(int _x) : x{(_x % getMod() + getMod()) % getMod()} {}
    ModInt(i64 _x) : x{(_x % getMod() + getMod()) % getMod()} {}

    static void setMod(i64 Mod_) {
        Mod = Mod_;
    }
    static i64 getMod() {
        return !P ? Mod : P;
    }
    explicit constexpr operator int() const {
        return x;
    }

    ModInt &operator += (ModInt a) & {
        x = x + a.x >= getMod() ? x + a.x - getMod() : x + a.x;
        return (*this);
    }
    ModInt &operator -= (ModInt a) & {
        x = x - a.x < 0 ? x - a.x + getMod() : x - a.x;
        return (*this);
    }
    ModInt &operator *= (ModInt a) & {
        (x *= a.x) %= getMod();
        return (*this);
    }
    constexpr ModInt inv() {
        return power((*this), getMod() - 2);
    }
    ModInt &operator /= (ModInt a) & {
        return (*this) *= a.inv();
    }
    friend ModInt operator + (ModInt lhs, ModInt rhs) {
        return lhs += rhs;
    }
    friend ModInt operator - (ModInt lhs, ModInt rhs) {
        return lhs -= rhs;
    }
    friend ModInt operator * (ModInt lhs, ModInt rhs) {
        return lhs *= rhs;
    }
    friend ModInt operator / (ModInt lhs, ModInt rhs) {
        return lhs /= rhs;
    }

    friend std::istream &operator >> (std::istream &is, ModInt &p) {
        return is >> p.x;
    }
    friend std::ostream &operator << (std::ostream &os, ModInt p) {
        return os << p.x;
    }
    int operator !() {
        return !x;
    }
    friend bool operator == (ModInt lhs, ModInt rhs) {
        return lhs.x == rhs.x;
    }
    friend bool operator != (ModInt lhs, ModInt rhs) {
        return lhs.x != rhs.x;
    }
    ModInt operator -() {
        return ModInt(getMod() - x);
    }
    ModInt &operator ++() & {
        ++x;
        return *this;
    }
    ModInt operator ++(int) {
        ModInt temp = *this;
        ++*this;
        return temp;
    }
} ;
template<>
i64 ModInt<0>::Mod = 1E9 + 7;
constexpr int P = 998244353;
using Z = ModInt<P>;
struct Comb {
    int n;
    vector<Z> _fac;
    vector<Z> _invfac;
    vector<Z> _inv;
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {init(n);}
    void init(int m) {
        m = min<int>(m, Z::getMod() - 1);
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        for (int i = n + 1; i <= m; i++) _fac[i] = _fac[i - 1] * i;
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        } n = m;
    }
    Z fac(int m) {if (m > n) init(2 * m); return _fac[m];}
    Z invfac(int m) {if (m > n) init(2 * m); return _invfac[m];}
    Z inv(int m) {if (m > n) init(2 * m); return _inv[m];}
    Z binom(int n, int m) {return n < m || m < 0 ? 0 : fac(n) * invfac(m) * invfac(n - m);}
} comb;
const int N = 3E4 + 5, M = 5E5 + 5;
int n, m, k;
int head[N], nex[M << 1], to[M << 1], cnt = 1;
bool bridge[M << 1];
int dfn[N], low[N], tot;
vector<int> vec[N];
void ad(int x, int y) {
	to[++cnt] = y;
	nex[cnt] = head[x];
	head[x] = cnt;
}
void add(int x, int y) {ad(x, y); ad(y, x);}
void tarjan(int x, int fr_edge) {
	dfn[x] = low[x] = ++tot;
	for (int i = head[x]; i; i = nex[i]) {
		int v = to[i];
		if (!dfn[v]) {
			tarjan(v, i);
			low[x] = min(low[x], low[v]);
			if (low[v] > dfn[x])
				bridge[i] = bridge[i ^ 1] = 1;
		} else if ((i ^ 1) != fr_edge)
			low[x] = min(low[x], dfn[v]);
	}
}
int t, dcc[N];
void dfs(int x) {
	dcc[x] = t;
	for (int i = head[x]; i; i = nex[i]) {
		int v = to[i];
		// cerr << x << ' ' << v << ' ' << dcc[x] << ' ' << dcc[v] << ' ' << bridge[i] << '\n';
		if (~dcc[v] || bridge[i]) continue;
		// cerr << "Dfs: " << x << "->" << v << "!\n";
		dfs(v);
	}
}
vector<array<int, 2>> e[N];
struct Matrix {
	int n;
	vector<vector<Z>> a;
	Matrix() {n = 0;}
	void Init(int _n) {
		n = _n;
		a.assign(n, vector<Z>(n, 0));
	}
	auto &operator[](int x) {return a[x];}
	int size() {return n;}
} ;
using K = Matrix;
Z det(K a) {
	bool sign = 0;
	Z ans = 1;
	const int n = a.size();
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			while (a[i][i].x > 0) {
				Z div = a[j][i].x / a[i][i].x;
				for (int k = 0; k < n; ++k)
					a[j][k] -= div * a[i][k];
				swap(a[i], a[j]); sign ^= 1;
			}
			swap(a[i], a[j]); sign ^= 1;
		}
	}
	for (int i = 0; i < n; ++i)
		ans *= a[i][i];
	return sign ? -ans : ans;
}
K a[N];
int id[N], tofa[N];
Z f[N][2], g[N][2];
void dp(int x, int fa) {
	// cerr << "Node " << x << ' ' << fa << ":\n";
	for (auto p : vec[x]) g[p][0] = 1;
	for (auto [v, fr] : e[x]) if (v != fa) {
		dp(v, x);
		// cerr << "ZHUANYIBIAN: " << v << ' ' << x << ' ' << fr << ' ' << g[fr][0] << ' ' << g[fr][1] << ' ' << f[v][0] << ' ' << f[v][1] << '\n';
		g[fr][1] = g[fr][1] * f[v][1] - g[fr][0] * f[v][0];
		g[fr][0] *= f[v][1];
	} else tofa[x] = fr;
	if (!~tofa[x]) tofa[x] = vec[x][0];
	// cerr << x << ' ' << fa << ' ' << tofa[x] << ' ' << " ?!?!\n";
	int sz = vec[x].size();
	a[x].Init(sz);
	for (int i = 0; i < sz; ++i) {int v = vec[x][i]; id[v] = i;}
	for (auto u : vec[x]) {
		for (int i = head[u]; i; i = nex[i]) {
			int v = to[i]; if (bridge[i]) continue;
			a[x][id[u]][id[v]] = 1;
		}
	}
	for (int i = 0; i < sz; ++i) {
		int v = vec[x][i];
		a[x][i][i] = g[v][1];
		for (int k = 0; k < sz; ++k) 
			if (k != i) a[x][i][k] *= g[v][0];
	}
	// cerr << sz << ' ' << "WTF\n";
	f[x][1] = det(a[x]);
	if (sz == 1) f[x][0] = g[vec[x][0]][0];
	else {
		K b; b.Init(sz - 1);
		for (int i = 0, _ = -1; i < sz; ++i) {
			if (vec[x][i] != tofa[x]) ++_;
			for (int j = 0, __ = -1; j < sz; ++j) {
				if (vec[x][j] != tofa[x]) ++__;
				// cerr << "index: " << _ << ' ' << __ << '\n';
				if (_ >= 0 && __ >= 0) b[_][__] = a[x][i][j];
			}
		}
		// cerr << "Matrix B:\n";
		// for (int i = 0; i < sz - 1; ++i) for (int j = 0; j < sz - 1; ++j)
		// 	cerr << b[i][j] << " \n"[j == sz - 2];
		f[x][0] = det(b) * g[tofa[x]][0];
	}
	// cerr <<"Debug:\n";
	// cerr << x << ' ' << f[x][0] << ' ' << f[x][1] << "!\n";
	// cerr << "Size: " << sz << '\n';
	// for (int i = 0; i < sz; ++i) cerr << vec[x][i] << ' ' << g[vec[x][i]][0] << ' ' << g[vec[x][i]][1] << '\n';
	// cerr << '\n';
	// for (int i = 0; i < sz; ++i, cerr << '\n') for (int j = 0; j < sz; ++j)
	// 	cerr << a[x][i][j] << ' ';
	// cerr << "------------------\n";
}
int main() {	
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> k;
	memset(tofa, -1, sizeof tofa);
	for (int i = 1; i <= m; ++i) {
		int u, v; cin >> u >> v;
		--u, --v; add(u, v);
	}
	tarjan(0, 0);
	fill(dcc, dcc + n, -1);
	for (int i = 0; i < n; ++i) if (!~dcc[i]) {
		dfs(i);
		++t;
	}
	for (int u = 0; u < n; ++u) {
		vec[dcc[u]].push_back(u);
		for (int i = head[u]; i; i = nex[i]) {
			int v = to[i];
			if (dcc[u] != dcc[v])
				e[dcc[u]].push_back({dcc[v], u});
		}
	}
	// for (int i = 0; i < n; ++i) cerr << dcc[i] << ' '; cerr << '\n';
	// cerr << cnt << '\n';
	// for (int i = 2; i <= cnt; ++i) if (bridge[i]) {
	// 	cerr << to[i] << " \n"[i & 1];
	// }
	// return 0;
	dp(0, 0);
	cout << (n & 1 ? -1 : 1) * f[0][1] << '\n';
}
/*
10 12 3
3 5
5 9
5 10
1 2
1 3
2 3
4 5
4 6
5 6
7 8
7 9
8 9

answer: 4
*/