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
1 2
4 3
Sample Output
8
【数据范围】
100%的数据，0＜n≤500000，1≤Ai，Bi≤n，0≤m≤n，保证没有人自恋。
把暗恋关系看作双向边，如果所有点度数都<=2，且没有环则有解。
否则不难发现每个连通分量是一条链，如果链上元素多于1则答案是2，否则答案是1。
每个连通分量肯定在一起，所以再将答案乘以连通分量个数的阶乘就行了。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=<<;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=,f=;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;
for(;isdigit(c);c=Getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int mod=;
const int maxn=;
int n,m,A[maxn],in[maxn],pa[maxn];
int findset(int x) {return pa[x]==x?x:pa[x]=findset(pa[x]);}
int main() {
n=read();m=read();
rep(i,,n) pa[i]=i;
rep(i,,m) {
int u=read(),v=read();
if(A[v]==u) continue;
if(findset(u)==findset(v)) {puts("");return ;}
pa[findset(u)]=findset(v);
in[v]++;in[u]++;A[u]=v;
}
int ok=,blo=;
rep(i,,n) {
if(in[i]>) ok=;
if(findset(i)==i) blo++;
}
if(!ok) puts("");
else {
ll ans=,cnt=;
rep(i,,blo) (ans*=i)%=mod;
rep(i,,n) if(!in[i]) cnt++;
rep(i,,blo-cnt) (ans*=)%=mod;
printf("%lld\n",ans);
}
return ;
}