[atARC153F]Tri-Colored Paths

称一条边在环外当且仅当其两端点不全在环上

用总方案数减去不合法的方案数，并分类讨论——

• Case1：图中不存在某种颜色的边

• 否则，若存在简单环的颜色集合为\(\{1,2,3\}\)，则环上每种颜色的边恰有一条

  否则，若颜色为\(1\)的边数\(\ge 2\)，则去掉其中一条后得到的简单路径矛盾

  记环上的节点为\(a_{[1,3]}\)（其中\(a_{i}\)的对边颜色为\(i\)），则\(a_{i}\)环外的出边颜色为\(i\)

  否则，若\((a_{1},x)\)的颜色为\(2\)，则\(x-a_{1}-a_{2}-a_{3}\)矛盾

  • Case2：仅有至多一个\(a_{i}\)有出边，则环外的边颜色均为\(i\)

  • 否则，若\(a_{i},a_{j}\)同时有出边，则出边（唯一且）端点相同

    否则，若\((a_{1},x),(a_{2},y)\)，则\(x-a_{1}-a_{2}-y\)矛盾

    Case3：记该端点为\(z\)，结合\((z,a_{i},a_{j})\)，整张图至多再有一条\((z,a_{6-i-j})\)的边

• 否则，若存在简单环的颜色集合为\(\{1,2\}\)，则环外的边颜色不为\(3\)

  否则，取该边到环上的一条路径，并将第一个交点两旁的一边断开后与环拼接

  显然两边不可能均为唯一的\(1,2\)，矛盾

  由于存在颜色为\(3\)的边，其两端点均在环上，进而得到颜色集合为\(\{1,2,3\}\)的简单环

  （颜色集合为\(\{1,3\}\)或\(\{2,3\}\)类似）

• 否则，即所有简单环上的边颜色均相同，进而每个点双内的边颜色均相同

  建立圆方树，问题即给每个方点（代表点双）染色，使得圆点间满足条件

  类似前者，讨论每个圆点周围方点的颜色集合，最终仅有以下情况——

  Case4：某个……颜色集合为\(\{1,2,3\}\)，且删去其后每块内方点颜色均相同

时间复杂度为\(O(n)\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005,mod=998244353;
int n,m,x,y,ans,st[N],dfn[N],low[N],cnt[N];
vector<int>e[N];
int add(int x,int y){
	x+=y;
	return (x<mod ? x : x-mod);
}
int qpow(int n,int m){
	int s=n,ans=1;
	while (m){
		if (m&1)ans=(ll)ans*s%mod;
		s=(ll)s*s%mod,m>>=1;
	}
	return ans;
}
int calc(int n){
	return (qpow(3,n)+3LL*(mod-qpow(2,n))+3)%mod;
}
void dfs(int k,int fa){
	st[++st[0]]=k;
	dfn[k]=low[k]=++dfn[0];
	for(int i:e[k])
		if (i!=fa){
			if (!dfn[i]){
				dfs(i,k),low[k]=min(low[k],low[i]);
				if (dfn[k]<=low[i]){
					cnt[k]++;
					while (st[st[0]]!=i)cnt[st[st[0]--]]++;
					cnt[st[st[0]--]]++;
				}
			}
			else low[k]=min(low[k],dfn[i]);
		}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	ans=calc(m);
	for(int i=1;i<=n;i++)
		if (e[i].size()==2){
			for(int j:e[i])
				if (e[j].size()==2){
					if ((j^e[i][0]^e[i][1])==(i^e[j][0]^e[j][1]))ans=add(ans,mod-3);
				}
		}
	if ((n==3)&&(m==3))ans=add(ans,12);
	if ((n==4)&&(m>4))ans=add(ans,mod-6);
	dfs(1,0);
	for(int i=1;i<=n;i++)ans=add(ans,mod-calc(cnt[i]));
	printf("%d\n",ans);
	return 0;
}