[HNOI/AHOI2018] 毒瘤

题目描述

从前有一名毒瘤。 毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题:给出一个数组,要求支持若干种奇奇怪怪的修改操作(比如区间加一个数,或者区间开平方),并支持询问区间和。毒瘤考虑了 $n$ 个这样的修改操作,并编号为 $1\sim n$。当毒瘤要出数据结构题的时候,他就将这些修改操作中选若干个出来,然后出成一道题。 当然了,这样出的题有可能不可做。通过精妙的数学推理,毒瘤揭露了这些修改操作的关系:有 $m$ 对“互相排斥”的修改操作,第 $i$ 对是第 $u_i$ 个操作和第 $v_i$ 个操作。当一道题同时含有 $u_i$ 和 $v_i$ 这两个操作时,这道题就会变得不可做。另一方面,一道题中不包含任何“互相排斥”的修改操作时,这个题就是可做的。此外,毒瘤还发现了一个规律:$m-n$ 是一个很小的数字,且任意两个修改操作都是连通的。两个修改操作 $a,b$ 是连通的,当且仅当存在若干操作 $t_0,t_1,\cdots,t_l$,使得 $t_0=a,t_l=b$,且对 $1\leq i\leq l$,$t_{i-1}$ 和 $t_i$ 都是“互相排斥”的修改操作。 一对“互相排斥”的修改操作称为互斥对。现在毒瘤想知道,给定值 $n$ 和 $m$ 个互斥对,他共能出出多少道可做的不同的数据结构题。两道数据结构题是不同的,当且仅当有一个修改操作在其中一道题中存在,而在另一道题中不存在。

输入输出格式

输入格式


第一行为正整数 $n,m$。 接下来 $m$ 行,每行两个正整数 $u,v$,代表一对“互相排斥”的修改操作。

输出格式


输出一行一个整数,代表毒瘤可以出的可做的不同的“互相排斥”的修改操作的个数。这个数可能很大,所以只输出模 $998244353$ 后的值。

输入输出样例

输入样例 #1

3 2
1 2
2 3

输出样例 #1

5

输入样例 #2

6 8
1 2
1 3
1 4
2 4
3 5
4 5
4 6
1 6

输出样例 #2

16

输入样例 #3

12 18
12 6
3 11
8 6
2 9
10 4
1 8
6 2
11 5
10 6
12 2
9 3
7 6
2 7
3 2
7 3
5 6
2 11
12 1

输出样例 #3

248

说明

#### 样例一说明 可做的题包括 $\varnothing,\{1\},\{2\},\{3\},\{1,3\}$。注意,**空集是合法的数据结构题**。 #### 数据范围 ![](https://cdn.luogu.com.cn/upload/pic/17511.png)