Obviously, the assignments of directions of edges can be considered independently for each connected component, and the number of assignments is represented as a product of the numbers of assignments of all connected components. So, we consider a single connected component first.

Assume that a connected component has \(N'\) vertices and \(M'\) edges. Then, each of the \(M'\) edges connects two of the \(N'\) vertices, and each of the edges connected to each of the \(N'\) vertices is one of the \(M'\) edges, so when we direct the edges in this graph, each vertex in this connected component and the edge incident to the vertex and another vertex should correspond correspond one-to-one. Therefore, in order for a desired assignment to exist, \(N' = M'\) is necessary; otherwise there are \(0\) ways of assignments.

Hereinafter we assume that \(M' = N'\). Since it does not have a self-loop or multi-edges, if \(N'=1\) then \(M'=0\) and if \(N'=2\) then \(M'=1\), so \(N'\geq 3\). Since the connected component consists of multiple vertices, each vertex is connected to other vertices with one or more edges. Here, let us divide into the following tow cases:

• If there exists a vertex such that it has exactly one incident edge

Let \(V_0\) be such vertex and \(E_0\) be the only incident edge. In order to achieve the objective, there must exist an edge that is directed from \(V_0\) to another vertex, so \(E_0\) should be directed from \(V_0\) to the other end. Now let us remove \(V_0\) and \(E_0\) from the graph; then it still results in a connected simple graph whose number of vertices and number of edges are equal. The number of possible assignments on the current graph is equal to the number of possible assignments on the original graph.

By repeating this operation, the number of vertices and edges decreases by one each, but after removing vertices and edges the degree (=the number of edges) of the graph should be at least \(3\), so this repetition ends after finite times, and boiled down to the other case.

• If every vertex has two or more incident edges

In this case, the sum of number of incident edges for each of \(N'\) vertex is at least \(2\times N'=2N'\); however, by the handshaking lemma, it is equal to \(2M'=2N'\), and the equality condition, for each vertex the number of its incident edges is \(2\). Therefore, this graph is a connected simple undirected graph where the degree of every vertex is \(2\), and thus a cycle. That is, there exists a permutation \((P_1, P_2, \ldots, P_{N'})\) of \((1,2,\ldots, N')\) such that Vertex \(P_i\) and Vertex \(P_{i+1}\) are connected with an edge, and so do Vertex \(P_{N'}\) and \(P_1\), but no other edges exist. In such case, once the direction of any edge is determined, the assignment of achieving the objective is uniquely determined; there are only two possible assignments:

• directing in the direction of \(P_i \rightarrow P_{i+1}\) (\(1\leq i\leq N'-1\)) and \(P_{N'}\rightarrow P_1\)
• directing in the direction of \(P_i \leftarrow P_{i+1}\) (\(1\leq i\leq N'-1\)) and \(P_{N'}\leftarrow P_1\)

To sum up, if \(N'=M'\) then there are exactly \(2\) ways to direct the edges while satisfying the condition.

Therefore, the answer for the problem is, if there exists a connected component whose number of vertices and whose number of edges are different, then the answer is \(0\); otherwise, the answer is \(2^K\), where \(K\) is the number of connected component. Note that the answer should be computed modulo \(998244353\).

The number of vertices and edges of each connected component can be computed in a total of \(O(N+M)\) time by performing DFS (Depth-First Search) from the not-visited-yet vertex. Therefore, the problem has been solved.

#include <bits/stdc++.h>

using namespace std;

#define N 200100
#define MOD 998244353
#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)
#define pb push_back

vector<int>e[N];
bool used[N];
int x, y;
void dfs(int k) {
	used[k] = true;
	x++;
	y += e[k].size();
	rep(i, e[k].size())if (!used[e[k][i]])dfs(e[k][i]);
	return;
}

int main(void) {
	int n, m;

	ll ans = 1;
	cin >> n >> m;
	rep(i, n)used[i] = false;
	rep(i, m) {
		cin >> x >> y;
		e[x - 1].pb(y - 1);
		e[y - 1].pb(x - 1);
	}
	rep(i, n) {
		if (!used[i]) {
			x = 0;
			y = 0;
			dfs(i);
			if (y == (x * 2))ans = (ans * 2) % MOD;
			else ans = 0;
		}
	}
	cout << ans << endl;

	return 0;
}