输入：
3 1
1 2
输出：
3
说明：
In the first sample, all valid permutations are \{1,2,3\},\{1,3,2\}{1,2,3},{1,3,2} and \{2,3,1\}{2,3,1}, so the answer is 33.
输入：
3 2
1 2
2 3
输出：
1
输入：
3 2
1 2
2 1
输出：
0
输入：
10 7
1 2
3 2
5 4
7 8
2 6
4 6
8 6
输出：
37800
题意：
给出n个点，m组关系(x,y)，要求下标为x的点要小于下标为y的点，保证x都不相同，问有几种组合。
思路：
显然是排列组合。
保证x都不相同，所以可以用并查集判是否存在环，若存在则答案为0(自相矛盾了)。
比赛时忘记了这个条件，读了个假题，可恶啊！
对样例4的答案怎么来的：
C
10
8
∗
A
2
2
∗
C
7
3
∗
C
4
2
∗
C
2
2
∗
C
2
1
{{C_{10}^{8}}}*{{A_{2}^{2}}}*{{C_{7}^{3}}}*{{C_{4}^{2}}}*{{C_{2}^{2}}}*{{C_{2}^{1}}}
C108∗A22∗C73∗C42∗C22∗C21
分别代表：
满足树的条件的个数 x 剩下无要求的数字的全排列 x 剩下的子树分别的要求。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int MOD=998244353;
const int N=2e6+10;
ll jc[N],jc_inv[N];
ll n,m,f[N],sum[N],vis[N],flag=0;
vector<int>g[N];
ll ans=1;
int fa[N];
ll v1[N],v2[N];//v1重置
int in[N],out[N];
//求逆元
ll inv(ll a,ll b)
{
ll ans1=1;
while(b)
{
if(b%2)
ans1=ans1*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ans1;
}
//求C
inline ll C(ll n,ll m)
{
if(m>=n)
return 1;
else
return jc[n]%MOD*jc_inv[m]%MOD*jc_inv[n-m]%MOD;
}
//求这棵子树的节点个数
int dfs(int vex)
{
if(sum[vex]>1) return sum[vex];
ll res=1;
for(int i=0;i!=g[vex].size();++i)
{
res+=dfs(g[vex][i]);
}
sum[vex]=res;
return res;
}
//求答案
void bfs1(int cnt,int vex)
{
queue<pair<ll,ll>> q;
for(int i=0;i!=g[vex].size();++i)
{
ans*=C(cnt-1,sum[g[vex][i]]);
ans%=MOD;
cnt-=(sum[g[vex][i]]);
q.push({sum[g[vex][i]],g[vex][i]});
}
while(q.size())
{
auto tmp=q.front();
int tt=tmp.first;
q.pop();
for(int i=0;i!=g[tmp.second].size();++i)
{
ans*=C(tt-1,sum[g[tmp.second][i]]);
ans%=MOD;
tt-=sum[g[tmp.second][i]];
q.push({sum[g[tmp.second][i]],g[tmp.second][i]});
}
}
}
//并查集模板——并查集判环
int get(int x)
{
if(fa[x]==0) return fa[x]=x;
return fa[x]==x?x:fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
fa[get(x)]=get(y);
}
int main()
{
scanf("%lld %lld",&n,&m);
jc[0]=1;
for(int i=1;i<=n;++i)
{
jc[i]=i*jc[i-1];
jc[i]%=MOD;
jc_inv[i]=inv(jc[i],MOD-2);
}
for(int i=1;i<=n;i++) sum[i]=1;
for(int i=1;i<=m;++i)
{
int x,y;scanf("%d%d",&x,&y);
g[y].pb(x);
f[x]=y;
if(get(x)==get(y))//已知x都不同，则若出现祖先相同，则一定出现了环
{
cout << 0 << endl;
return 0;
}
merge(x,y);
}
for(int i=1;i<=n;++i)
{
if(f[i]==0)//从根节点开始算
dfs(i);
}
int nn=n;
for(int i=1;i<=nn;++i)
{
if(f[i]==0)
{
ans*=C(n,sum[i]);
ans%=MOD;
n-=sum[i];
bfs1(sum[i],i);
}
}
cout << ans << endl;
}