#2496. 「AHOI / HNOI2018」毒瘤

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: SYCstudio

题目描述

从前有一名毒瘤。

毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题:给出一个数组,要求支持若干种奇奇怪怪的修改操作(例如给一个区间内的数同时加上 cc,或者将一个区间内的数同时开平方根),并且支持询问区间的和。毒瘤考虑了 nn 个这样的修改操作,并将它们编号为 1...n1 ... n。当毒瘤要出数据结构题的时候,他就将这些修改操作中选若干个出来,然后出成一道题。

当然了,这样出的题有可能不可做。通过精妙的数学推理,毒瘤揭露了这些修改操作之间的关系:有 mm 对“互相排斥”的修改操作,第 ii 对是第 uiu_i 个操作和第 viv_i 个操作。当一道题中同时含有 uiu_iviv_i 这两个操作时,这道题就会变得不可做。另一方面,当一道题中不包含任何“互相排斥”的操作时,这个题就是可做的。此外,毒瘤还发现了一个规律:mnm − n 是一个很小的数字(参见“数据范围”中的说明),且任意两个修改操作都是连通的。两个修改操作 a,ba, b 是连通的,当且仅当存在若干操作 t0,t1,...,tlt_0, t_1, ... , t_l,使得 t0=a,tl=bt_0 = a,t l = b,且对任意 1il1 \le i \le lti1t_{i−1}tit_i 都是“互相排斥”的修改操作。

一对“互相排斥”的修改操作称为互斥对。现在毒瘤想知道,给定值 nnmm 个互斥对,他一共能出出多少道可做的不同的数据结构题。两个数据结构题是不同的,当且仅当其中某个操作出现在了其中一个题中,但是没有出现在另一个题中。

输入格式

第一行为正整数 n,mn, m

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

输出格式

输出一行一个整数,表示毒瘤可以出的可做的不同的数据结构题的个数。这个数可能很大,所以只输出模 998244353998244353 后的值。

样例

样例输入 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

数据范围与提示

HNOI2018-3