Description：

$n$ 个点， $m$ 条边，第 $i$ 条边的权值是 $2^i$ ，每条边可以重复经过，求一个欧拉回路使得经过的总边权和最小。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

既然边的权值是二的幂，那么就满足贪心性质，先把所有奇度数点找出来，这样的点一定有偶数个，然后把所有边一定都是要走一遍的，然后可以猜一个结论，就是剩下的奇度数点一定两两配对，也就是说从一个点走到另一个点，然后由于可以贪心，所以把这个图的最小生成树求出来，匹配一定在这棵树上，因为我们宁愿走所有小边权边也不愿走一个大边权边，所以做一个树形 $DP$ 把这个匹配求出来即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

#define MAXN 500010

#define MOD 998244353

typedef long long ll;

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = (ll)res * (ll)a % MOD;

		a = (ll)a * (ll)a % MOD;

		b = b >> 1;

	}

	return res;

}

int n,m;

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int fa[MAXN];

int find(int x){return (fa[x] == x ? x : fa[x] = find(fa[x]));}

int ans = 0;

int ind[MAXN];

bool tag[MAXN];

int f[MAXN];

int siz[MAXN];

bool v[MAXN];

void dp(int k)

{

	v[k] = true;

	if(tag[k])siz[k] = 1;

	else siz[k] = 0;

	f[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp(e[i].to);

		if((siz[e[i].to] % 2) == 0)f[k] = (f[k] + f[e[i].to]) % MOD;

		else f[k] = (f[k] + (power(2,e[i].v) + f[e[i].to]) % MOD) % MOD;

		siz[k] += siz[e[i].to];

	}

	return;

}

int main()

{

	freopen("B.in","r",stdin);

	freopen("B.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)fa[i] = i;

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		a = read();b = read();

		ans = (ans + power(2,i)) % MOD;

		++ind[a];++ind[b];

		if(find(a) == find(b))continue;

		else

		{

			add(a,b,i);

			fa[find(a)] = find(b);

		}

	}

	for(int i = 1;i <= n;++i)if((ind[i] % 2) == 1)tag[i] = true;

	memset(v,false,sizeof(v));

	dp(1);

	cout << (ans + f[1]) % MOD << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}