题目描述：

对于一个无向图 $G$，三元组 $(a, b, c)$ 被称为优秀的当且仅当满足如下条件：

$1. a < b < c$；

$2. a $ 与 $b$ 有边相连；

$3. a $ 与 $c$ 有边相连；

$4. b$ 与 $c$ 没有边相连。

现在有一个 $n$ 个点的连通无向图 $G$，每次找一个优秀的三元组 $(a, b, c)$ 将 $b$ 和 $c$ 连边，如果没有则结束加边过程。

问最终得到的图有多少种用 $n$ 种颜色对点染色的方案，对 $998244353$ 取模后输出。

一种染色方案合法当且仅当每个点颜色是 $1$ 到 $n$ 中的一个，并且一条边两端的点颜色不同。

算法标签：线段树合并

思路：

对于一个无向图 $G$，三元组 $(a, b, c)$ 被称为优秀的当且仅当满足如下条件：

$1. a < b < c$；

$2. a $ 与 $b$ 有边相连；

$3. a $ 与 $c$ 有边相连；

$4. b$ 与 $c$ 没有边相连。

现在有一个 $n$ 个点的连通无向图 $G$，每次找一个优秀的三元组 $(a, b, c)$ 将 $b$ 和 $c$ 连边，如果没有则结束加边过程。

问最终得到的图有多少种用 $n$ 种颜色对点染色的方案，对 $998244353$ 取模后输出。

一种染色方案合法当且仅当每个点颜色是 $1$ 到 $n$ 中的一个，并且一条边两端的点颜色不同。

以下代码：

#include
      
       #define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=1e6+5,p=998244353;int n,m,rt[N],fa[N],cnt,tot,head[N],ne[N<<1],to[N<<1],ans=1;struct node{    int x,l,r,num;}t[N*21];il int read(){   int x,f=1;char ch;   _(!)ch=='-'?f=-1:f;x=ch^48;   _()x=(x<<1)+(x<<3)+(ch^48);   return f*x;}il void ins(int x,int y){    ne[++tot]=head[x];    head[x]=tot;to[tot]=y;}il int getfa(int x){    return fa[x]?(fa[x]=getfa(fa[x])):x;}il void update(int x){    t[x].num=t[t[x].l].num+t[t[x].r].num;}il void insert(int &x,int l,int r,int pos){    if(!x)x=++cnt;    if(l==r){t[x].num=1;return;}    int mid=(l+r)>>1;    if(pos<=mid)insert(t[x].l,l,mid,pos);    else insert(t[x].r,mid+1,r,pos);    update(x);}il void merge(int &x,int y,int l,int r){    if(!x||!y){x=x+y;return;}    if(l==r){t[x].num=1;return;}    int mid=(l+r)>>1;    merge(t[x].l,t[y].l,l,mid);    merge(t[x].r,t[y].r,mid+1,r);    update(x);}il int query(int x,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr)return t[x].num;    int mid=(l+r)>>1;int res=0;    if(ql<=mid)res=query(t[x].l,l,mid,ql,qr);    if(mid