QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 256 MB Total points: 100 Hackable ✓

# 4259. 胡策的统计

统计

在 OI 界,有一位无人不知无人不晓,OI 水平前无古人后无来者的胡策,江湖人称一眼秒题胡大爷!

今天胡策在研究无向图的连通性。对于一个无向图定义它的连通值为该图连通块数的阶乘。

为了研究连通值的性质,胡策随手画了一个 $n$ 个结点的简单无向图 $G$,结点分别编号为 $1, \dots, n$,他想统计出 $G$ 的所有生成子图的连通值之和。

胡策当然会做啦!但是他想考考你。你只用输出结果对 $998244353$ ($7 \times 17 \times 2^{23} + 1$,一个质数) 取模后的结果。

简单无向图即无重边无自环的无向图。生成子图即原图中删去若干条边(可以是 $0$ 条)后形成的图。

输入格式

第一行两个整数 $n, m$,表示 $G$ 的结点数和边数。保证 $n \geq 1,m \geq 0$。

接下来 $m$ 行,每行两个整数 $v, u$,表示 $v$ 号结点和 $u$ 号结点之间有一条无向边。保证 $1 \leq v, u \leq n$,保证没有重边和自环。

输出格式

一行,一个整数表示答案。

样例一

input

6 13
1 2
1 3
2 3
1 4
4 2
3 4
5 2
3 5
5 4
6 2
6 3
6 4
6 5


output

16974


样例二

见样例数据下载。

限制与约定

测试点编号 $n$ 特殊限制
1$\leq 6$
2$\leq 10$
3
4$\leq 17$
5
6
7$\leq 20$$G$ 为完全图
8
9
10

时间限制:$3\texttt{s}$

空间限制:$256\texttt{MB}$

来源

中国国家集训队互测2015 - By 吕凯风