UOJ Logo Universal Online Judge

UOJ

#193. 【UR #14】人类补完计划

统计

在经过了多次失败后,跳蚤国王终于成功地制造出了第一个也是唯一一个最强跳蚤——跳蚤属性储备的不足使得量产最强跳蚤的计划化作了泡影。但是即使只有一个最强跳蚤,战争的局势还是渐渐地被逆转了——最强跳蚤每次可以带着几百只跳蚤跳到 pion 吧的腹地进行骚扰。腹背受敌的人类渐渐陷入了劣势。

为局势所迫,人类的领袖_叫我猪猪侠决定和跳蚤国一样,制造属于自己阵营的超级士兵——这个计划被人们称作人类补完计划。

每一个人的遗传物质中都有许多的基因节点,基因节点之间又被基因链相连——这可以看做一张 $n$ 个点 $m$ 条边的无向图——它们构成了人类的基因图。然而在人类的基因图中,并不是所有的都是优秀的基因,例如傲慢、妒忌、暴怒、懒惰、贪婪、饕餮和色欲,它们就是负面的。

在人类补完计划中,人类将删去基因图中不好的基因链以及没有被任何基因链连接的孤立的基因节点,来达成补全人类优秀基因的目的。

为了得到最优的方案,科学家们需要对人类的基因图进行多方面的评估。其中有一项简要来讲是这样的,就是给出一张$n$个点$m$条边的基因图,对于一个边集的子集$S_e$,我们把所有与$S_e$中至少一条边相邻的点形成的集合称为$S_v$,$S_e$被称为好的当且仅当:

  1. $|S_e| = |S_v|$。
  2. 对于$S_v$中不同的两个点$x$和$y$,存在一条从$x$到$y$的路径使得路径中的边都属于$S_e$。

设所有与$S_e$中大于一条边相邻的点的数量为$w$,那么这个边集的权值为$2 ^ w$。一张基因图的权值是所有好的边集的权值和。

现在_叫我猪猪侠想要知道他自己的基因图的权值,但是因为战争事务实在太过繁杂,所以他决定让你——一个刚刚从前线抓来的为跳蚤办事的人类叛徒来帮他计算答案。

输入格式

第一行两个正整数 $n, m$,含义如题意所述。

接下来的$m$行中,第$i$行有两个整数$x_i, y_i$,表示$x_i$与$y_i$之间有一条无向边。

输出格式

一行一个整数,表示这张基因图的权值对$998244353$取模的值。

样例一

input

3 3
1 3
2 3
1 2

output

8

explanation

唯一的好的边集就是所有边组成的集合,由于所有点都与边集中两条边相邻,所以权值为$2 ^ 3 = 8$。

样例二

input

3 2
1 2
1 3

output

0

explanation

不存在好的边集。

样例三

input

4 4
1 2
1 3
2 3
1 4

output

16

explanation

整数$x$表示输入的第$x$条边。 好的边集为$\{1, 2, 3\}$, $\{1, 2, 3, 4\}$,在两个边集中$4$号点分别与0条和1条边相邻,都不会算入$w$中,而其他三个点都至少与2条边相邻,因此两个边集的权值均为$8$,答案为$8 + 8 = 16$。

样例四

input

5 5
1 2
1 3
2 3
1 4
4 5

output

32

explanation

好的边集为$\{1, 2, 3\}$, $\{1, 2, 3, 4\}$, $\{1, 2, 3, 4, 5\}$,前两个边集的权值为8,最后一个边集的权值为16,答案为$8 + 8 + 16 = 32$。

样例五

input

6 10
5 3
4 3
2 3
1 6
5 6
2 6
1 5
1 4
6 3
3 1

output

4544

样例六

见样例数据下载,这组数据中$n = 14$,$m = 90$,请注意答案要对$998244353$取模。

限制与约定

每组测试数据的限制与约定如下所示:

测试点编号 n m
1$n \le 11$$m \le 20$
2保证每个点最多只能直接或间接到达6个其他的点。
3
4
5
6
7$n \le 14$
8
9
10
11$n \le 15$$m = \frac{n(n - 1)}{2}$
12
13
14
15$n \le 16$$m = \frac{n(n - 1)}{2}$
16
17
18
19
20

对于所有数据, $1 \le n \le 16$, $0 \le m \le \frac{n(n - 1)}{2}$。

$1 \le x_i, y_i \le n$,$x_i \ne y_i$,两个点之间最多只有一条边。

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

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

下载

样例数据下载