You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个含 $n$ 个点，$m$ 条边的有向图，图无重边，无自环，两点之间不成环。

现在我们想改变一些边的方向，使得该有向图无环。

您需要求出，每一种改变方向后使得该有向图无环的方案的需改变边的数量之和 $\bmod\ 998244353$ 之后的答案。

输入格式

第一行为两个整数 $n,m$。

接下来 $m$ 行，一行两个整数 $a_i,b_i$，表示有一条起点为 $a_i$，终点为 $b_i$ 的有向边。

输出格式

仅一行一个整数，表示每一种改变方向后使得该有向图无环的方案的需改变边的数量之和 $\bmod\ 998244353$ 之后的答案。

2 1
1 2

1

3 3
1 2
2 3
1 3

9

提示

样例解释

样例 1 解释

有如下两种方案：

• 改变方向。
• 不改变方向。

所以输出 $1+0=1$。

样例 2 解释

共有六种可行的方案：

• $1\to2,2\to3,1\to3$
• $1\to2,3\to2,1\to3$
• $1\to2,3\to2,3\to1$
• $2\to1,2\to3,1\to3$
• $2\to1,2\to3,3\to1$
• $2\to1,3\to2,3\to1$

所以输出 $0+1+2+1+2+3=9$。

数据范围

对于 $100\%$ 的数据，保证 $1\le n\le 18$，$0\le m\le \frac{n\times (n-1)}{2}$，$1\le a_i,b_i\le n$，$a_i\not=b_i$，对于 $i\not=j$，均有 $a_i\not=a_j$ 或者 $b_i\not=b_j$，无序数对 $\{a_i,b_i\}$ 互不相同。

详细子任务限制及分值如下表：

说明

本题译自 Central-European Olympiad in Informatics 2019 Day 2 T1 Amusement Park。