题目描述

Description

高三的学长们就要离开学校，各奔东西了。某班n人在举行最后的离别晚餐时，饭店老板觉得十分纠结。因为有m名学生偷偷找他，要求和自己暗恋的同学坐在一起。
饭店给这些同学提供了一个很长的桌子，除了两头的同学，每一个同学都与两个同学相邻（即坐成一排）。给出所有信息，满足所有人的要求，求安排的方案总数（这个数字可能很大，请输出方案总数取余989381的值，也可能为0）。

Input

输入有m+1行，第一行有两个用空格隔开的正整数n、m，如题所示。接下来的m行，每一行有两个用空格隔开的正整数，第i行为Ai和Bi，表示Ai的暗恋对象为Bi，保证Ai互不相等。

Output

输出只有一行，这一行只有一个数字，如题所示。

Sample Input

4 2
1 2
4 3

Sample Output

8

【数据范围】
100%的数据，0＜n≤500000，1≤Ai，Bi≤n，0≤m≤n，保证没有人自恋。

题目分析

记录每个人的度数 如果一个人的度数大于3 一定无解
最后建出来的是有向图 如果有环一定无解
然后每个联通块 包含点的数量如果大于1可以有两种排列方式
因为每个联通块互不干扰 然后就是全排列的问题了

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
long long ans=1;
int tot;
int f[500100];
int fa[500100];
int du[500100];
int cnt[500100];
int mod=989381;
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int x,i=1;i<=m;i++)
    {
        scanf("%d",&x);
        scanf("%d",&fa[x]);
        if(fa[fa[x]]==x) continue;
        int dx=find(x),dy=find(fa[x]);
        if(dx==dy||du[x]>=2||du[fa[x]]>=2) { printf("0"); return 0; }
        du[x]++,du[fa[x]]++,f[dx]=f[dy];
    }
    for(int i=1;i<=n;i++) cnt[find(i)]++;
    for(int i=1;i<=n;i++)
    {
        if(cnt[i]==1) tot++;
        else if(cnt[i]>=2)
            ans=ans*2%mod,tot++;
    }
    for(int i=1;i<=tot;i++) ans=ans*i%mod;
    printf("%lld",ans);
    return 0;
}