1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
enum{N=20,M=1<<18|10,P=998244353};
struct U{
int x;
U(){ } U(int x):x(x){ }
inline void operator += (const U &t){ x+=t.x,x>=P&&(x-=P); }
inline void operator -= (const U &t){ x-=t.x,x<0&&(x+=P); }
inline U operator * (const U &t){ return U(static_cast<unsigned long long>(x)*t.x%P); }
}I[N],F[M][N],H[M][N];
int n,m,G[N],C[M],B[M];
void FWT(int f) {
for(int i=1;i<m;i<<=1) {
for(int l=0;l<m;l+=i*2) {
for(int j=l;j<l+i;++j) {
if(f==1) rep(d,1,n) F[j+i][d]+=F[j][d];
else rep(d,1,n) F[j+i][d]-=F[j][d];
}
}
}
}
void Exp(U *a){
static U b[N];
rep(i,0,n-1) b[i]=a[i+1]*(i+1);
rep(i,0,n-1) {
U t=b[i];
rep(j,1,i) t+=a[j]*b[i-j];
a[i+1]=t*I[i+1];
}
}
int main(){
scanf("%d%d",&n,&m);
if(n==1) return puts("1"),0;
for(int x,y;m--;) scanf("%d%d",&x,&y),x--,y--,G[x]|=1<<y,G[y]|=1<<x;
I[0]=I[1]=1,m=1<<n;
rep(i,0,n-1) B[1<<i]=i;
rep(i,2,n) I[i]=U(P-P/i)*I[P%i];
rep(i,1,m-1) C[i]=C[i&(i-1)]+1;
rep(st,0,n-1) {
H[1<<st][st]=1;
rep(S,0,m-1) rep(i,st,n-1) if(H[S][i].x) {
for(int T=G[i]&~S;T;T&=T-1)
H[S|(T&-T)][B[T&-T]]+=H[S][i];
if(G[i]&(1<<st)) F[S][C[S]]+=H[S][i]*I[1+(C[S]>2)];
H[S][i]=0;
}
}
FWT(1);
for(int i=1;i<m;i<<=1){
for(int l=0;l<m;l+=i*2) for(int j=l;j<l+i;++j) {
rep(k,1,n) F[j+i][k]-=F[j][k];
Exp(F[j+i]+1);
rep(k,1,n) F[j+i][k]+=F[j][k];
}
}
FWT(-1),printf("%d\n",F[m-1][n].x);
}
|
