辺の向きの割り当て方は、明らかに連結成分ごとに独立に考えることができ、割り当てる方法の数はそれぞれの連結成分に対する割り当て方の積で表されます。よって、各連結成分について考えることにします。

ある連結成分の頂点数が \(N'\) 、辺の数が \(M'\) であったとします。 このとき \(M'\) 本の辺はすべて \(N'\) 個の頂点のうちのいずれか \(2\) つを結んでおり、一方、\(N'\) 個の各頂点から出ているすべての辺も \(M'\) 本の辺のいずれかであるので、このグラフの辺を向き付けたとき、この連結成分の各頂点とその頂点から他の頂点へのびる辺は \(1\) 対 \(1\) に対応しなければなりません。これより、条件をみたす割り当て方が存在するためには \(N'=M'\) である必要があり、そうでないとき \(0\) 通りとなります。

以下、\(M'=N'\) がみたされていると仮定します。 自己ループや多重辺が存在しないことより、\(N'=1\) ならば \(M'=0\) 、\(N'=2\) ならば \(M'=1\) であるため、\(N'\geq 3\) です。複数の頂点からなる連結成分であることから、それぞれの頂点は \(1\) 本以上の辺によって、他の頂点と結ばれています。 ここで、次のような場合分けを考えます。

• ある頂点が存在して、その頂点と他の頂点を結ぶ無向辺がちょうど \(1\) 本であるようなものが存在するとき

このときそのような頂点を \(V_0\), そこから伸びている唯一の辺を \(E_0\) とすると、条件をみたす向き付けを達成するためには、\(V_0\)から他の頂点へ向かう方向の辺が存在する必要があり、\(E_0\) は \(V_0\) からもう一方の端点へ向かう方向へ向き付けされなければなりません。このとき、\(V_0\) および \(E_0\) を削除したものを考えるとこれは連結な単純グラフでありやはり頂点数と辺数が一致しています。このグラフについての条件をみたす向き付け方と元のグラフについての条件をみたす向き付け方の数は一致します。

この操作を繰り返すことを考えると、この操作によってグラフの頂点の数はちょうど \(1\) ずつ減少しますが、上でも述べたように頂点と辺を削除した後のグラフの頂点数(=辺数)は \(3\) 異常である必要があるため、この作業は有限回で終了し、次の場合へ帰着できます。

• どの頂点についても、その頂点と他の頂点を結ぶ無向辺が \(2\) 本以上存在するとき

このとき、\(N'\) 個の頂点すべてについて、その頂点と他の頂点を結ぶ辺の本数の総和は \(2\times N'=2N'\) 以上となりますが、握手の定理よりこれは\(2M'=2N'\) に等しくなり、等号成立条件よりすべての頂点についてその頂点と他の頂点を結ぶ辺の本数は \(2\) となります。よって、これはすべての頂点の次数が \(2\) であるような連結な単純無向グラフであるのでサイクルとなっていることがわかります。すなわち、\((1,2,\ldots, N')\) のある並び替え \((P_1, P_2, \ldots, P_{N'})\)について、\(1\leq i\leq N'-1\) について頂点 \(P_i\)と頂点 \(P_{i+1}\) および頂点 \(P_{N'}\) と頂点 \(P_1\) が、かつそれらだけが結ばれているようなグラフとなっている事が分かります。このとき、これを条件みたすように向き付ける方法はどれか \(1\) 本の向き付けの方向を定めると一意に定まり、

• \(P_i \rightarrow P_{i+1}\) (\(1\leq i\leq N'-1\)) および \(P_{N'}\rightarrow P_1\)の方向に向き付ける
• \(P_i\leftarrow P_{i+1}\) (\(1\leq i\leq N'-1\)) および \(P_{N'}\leftarrow P_1\)の方向に向き付ける

の\(2\) 通りしかありません。 以上をあわせると、\(N'=M'\) のときはつねにちょうど \(2\) 通りの条件をみたす向き付けの方法があることが分かります。

ゆえに元の問題の答えは、ある連結成分についてその頂点数と辺数が一致していないならば \(0\) 通り、すべて一致しているならば、連結成分の個数を \(K\) として \(2^K\) 通りとなります。 \(998244353\) で割った余りを求めることに注意してください。

各連結成分の頂点数と辺数および連結成分の個数はまだ訪れていない頂点から始めてDFSを行うことを繰り返すことで、 \(O(N+M)\) で求めることができます。よって、この問題を解くことが出来ました。

#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;
}