#3165. 「CEOI2019」游乐园

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

题目描述

译自 CEOI 2019 Day2 T1「Amusement Park

你有一个 n 个节点的有向图,我们称一个合法的方案是将其中一些边的方向翻转之后使得剩下的图无环。请对于所有合法的方案,将方案中翻转方向的边的数量求和。

答案对 998244353 取模。

输入格式

第一行两个正整数 n,m ,表示节点数量和边的数量。

接下来 m 行每行两个正整数 a, b ,表示一条有向边 (a, b) ,保证 a \neq b 且输入的 {a, b} 互不相同。

输出格式

输出一个整数,表示所求的答案取模后的值。

样例

样例输入 1

2 1
1 2

样例输出 1

1

样例解释 1

有两种可行方案:

  1. 不翻转这条边,翻转边数为 0
  2. 翻转这条边,翻转边数为 1

样例输入 2

3 3
1 2
2 3
1 3

样例输出 2

9

样例解释 2

6 种合法方案:

  1. 方向为 (1, 2), (2, 3), (1, 3) ,翻转边数为 0
  2. 方向为 (1, 2), (3, 2), (1, 3) ,翻转边数为 1
  3. 方向为 (1, 2), (3, 2), (3, 1) ,翻转边数为 2
  4. 方向为 (2, 1), (2, 3), (1, 3) ,翻转边数为 1
  5. 方向为 (2, 1), (2, 3), (3, 1) ,翻转边数为 2
  6. 方向为 (2, 1), (3, 2), (3, 1) ,翻转边数为 3

数据范围与提示

对于 100\% 的数据,保证 1\le n \le 18, 0\le m \le \frac{n(n-1)}2

子任务编号 n 分值
1 \le 3 7
2 \le 6 12
3 \le 10 23
4 \le 15 21
5 \le 18 37