[AdditionalFile3165.zip](file://AdditionalFile3165.zip?type=additional_file)

#3165. 「CEOI2019」游乐园

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

译自 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. 不翻转这条边，翻转边数为 $0$。
2. 翻转这条边，翻转边数为 $1$。

样例 2

输入

3 3
1 2
2 3
1 3

输出

9

有 $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$。