P4426 [HNOI/AHOI2018]毒瘤

题目描述

从前有一名毒瘤。

毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题：给出一个数组，要求支持若干种奇奇怪怪的修改操作（比如区间加一个数，或者区间开平方），并支持询问区间和。毒瘤考虑了$n$个这样的修改操作，并编号为$1$~$n$。当毒瘤要出数据结构题的时候，他就将这些修改操作中选若干个出来，然后出成一道题。

当然了，这样出的题有可能不可做。通过精妙的数学推理，毒瘤揭露了这些修改操作的关系：有$m$对“互相排斥”的修改操作，第$i$对是第$u_i$个操作和第$v_i$个操作。当一道题同时含有$u_i$和$v_i$这两个操作时，这道题就会变得不可做。另一方面，一道题中不包含任何“互相排斥”的修改操作时，这个题就是可做的。此外，毒瘤还发现了一个规律：$m-n$是一个很小的数字，且任意两个修改操作都是连通的。两个修改操作$a,b$是连通的，当且仅当存在若干操作$t_0,t_1,...,t_l$，使得$t_0=a,t_l=b$，且对$1≤i≤l$，$t_{i-1}$和$t_i$都是“互相排斥”的修改操作。

一堆“互相排斥”的修改操作称为互斥对。现在毒瘤想知道，给定值$n$和$m$个互斥对，他共能出出多少道可做的不同的数据结构题。两道数据结构题是不同的，当且仅当有一个修改操作在其中一道题中存在，而在另一道题中不存在。

输入输出格式

第一行为正整数$n,m$。

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

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

输入输出样例

3 2
1 2
2 3

5

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

16

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

248

说明

样例一说明：可做的题包括空集,{1},{2},{3},{1,3}。注意，空集是合法的数据结构题。

数据范围

$n≤10^5,n-1≤m≤n+10$。