Description：

对于一个无向图 $G$ ，每次找到一个三元组 $(a,b,c)$ 满足 $a<b<c$ 并且 $ab$ ， $ac$ 相连但 $bc$ 不相连，把他们连起来，问最后用 $n$ 种颜色染色，要求每条边两端颜色不同，求方案数。

$1\leqslant n\leqslant 10^6$

Solution：

首先会发现一个点会把他所有往编号比他大的有连边的点连成一个团，并且这个点也在团中。那么考虑最终已经连好边了，怎么求方案数，我们从编号大的往编号小的依次计算，那么每个点染色的方案数就是 $n-$ 与它有连边的标号比它大的点的个数。考虑怎么计算在最终图中与它有连边的比他标号大的点的个数，可以发现最终图中 $u$ 和 $v$ 有边当且仅当在原图中存在一条从 $u$ 到 $v$ 的路径使得路径中间的点 $<\min(u,v)$ ，这样每次找到最小的点会把两个点之间连一条边，我们可以这样做：按编号从小往大考虑每个点，每次把这个点加入并查集中，然后我们实际上要求的就是在加入这个点后和这个点所在连通块相邻但是还没有连起来的点的个数，这些点编号一定比它大，因为还没有连边，并且路径上的点都小于两个端点，于是对于每个点开一个 $set$ 记录他的邻居，每次合并的时候就把 $set$ 启发式合并一下，并删去这次合并的点即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	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;

}

int n,m;

#define MAXN 1000010

set<int> s[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	if(a > b)e[++edgenum] = (edge){b,lin[a]},lin[a] = edgenum,s[b].insert(a);

	if(a < b)e[++edgenum] = (edge){a,lin[b]},lin[b] = edgenum,s[a].insert(b);

	return;

}

int id[MAXN];

int f[MAXN];

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

#define P 998244353

void merge(int &a,int &b)

{

	if(s[a].size() < s[b].size())swap(a,b);

	for(set<int>::iterator it = s[b].begin();it != s[b].end();++it)s[a].insert(*it);

	return;

}

int main()

{

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

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

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

	for(int i = 1;i <= m;++i)add(rd(),rd());

	for(int k = 1;k <= n;++k)id[k] = k;

	int ans = 1;

	for(int k = 1;k <= n;++k)

	{

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

		{

			if(find(e[i].to) == k)continue;

			s[id[find(e[i].to)]].erase(k);

			merge(id[k],id[find(e[i].to)]);

			f[find(e[i].to)] = k;

		}

		ans = 1ll * ans * (n - s[id[k]].size()) % P;

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}