rt，写的 O(nm) 但是在 11~15 点上 WA 了，不知道为什么，好像很多人也是这样。

思路是将 1 拿出图中，剩下会形成一些连通块，对于这些连通块中连着 1 的点作为起点进行 dp。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
const int inv2=499122177;
int qpow(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int n,m; vector<int> e[500010];
bool link1[500010];
int tot=0; vector<int> ltk[500010];
bool vis[500010];
void dfs1(int u,int fa)
{
	ltk[tot].push_back(u),vis[u]=1;
	for(int v:e[u])
	{
		if(v==fa) continue;
		dfs1(v,u);
	}
}
int siz[500010];
void dfs2(int u,int fa)
{
	siz[u]=1;
	for(int v:e[u])
	{
		if(v==fa) continue;
		dfs2(v,u);
		siz[u]+=siz[v];
	}
}
int ans[500010],dp[500010];
void dfs3(int u,int fa)
{
	if(fa==0) dp[u]=1;
	else dp[u]=(dp[fa]+1+(siz[fa]-1-siz[u])*inv2)%mod;
	for(int v:e[u])
	{
		if(v==fa) continue;
		dfs3(v,u);
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1; i<=m; ++i)
	{
		int u,v; cin>>u>>v;
		if(u>v) swap(u,v);
		if(u==1) link1[v]=1;
		else e[u].push_back(v),e[v].push_back(u);
	}
	for(int i=2; i<=n; ++i)
	{
		if(!vis[i]) ++tot,dfs1(i,0);
	}
	for(int i=1; i<=tot; ++i)
	{
		int cnt=0;
		for(int j:ltk[i]) cnt+=link1[j];
		int invcnt=qpow(cnt,mod-2);
		for(int j:ltk[i])
		{
			if(link1[j])
			{
				dfs2(j,0),dfs3(j,0);
				for(int j:ltk[i]) ans[j]=(ans[j]+dp[j]*invcnt)%mod;
			}
		}
		for(int j:ltk[i]) ans[j]=(ans[j]+1+(n-1-ltk[i].size())*inv2)%mod;
	}
	ans[1]=1;
	for(int i=1; i<=n; ++i) cout<<ans[i]<<' ';
	return 0;
}