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.

时空限制

1S/256M

题目描述

给定一张包含 $n$ 个顶点和 $m$ 条边的无向简单图（图可能不连通）。请问该图可能由多少种无向简单连通二分图通过删除两条边后得到。

连通图：图中任意两个顶点之间都存在路径。

二分图：图的顶点集可以划分为两个互不相交的子集 $U$ 和 $V$，使得图中的每条边都连接 $U$ 中的一个顶点和 $V$ 中的一个顶点（即图中不存在连接同一子集内部顶点的边）。

简单图：图中不含重边（连接同一对顶点的多条边）和自环（连接同一顶点的边）。

由于结果可能很大，请输出图的数量对 $998244353$ 取模后的结果。

格式

输入格式

第一行包含两个整数 $n,m$，表示无向图有 $n$ 个点，$m$ 条边。

接下来 $m$ 行，每行两个整数 $u,v$ 表示连接 $u,v$ 两点。

输出格式

输出一个数字，表示图的数量对 $998244353$ 取模的结果。

样例

样例输入 #1

4 2
1 3
2 4

样例输出 #1

2

数据规模

对于 $30\%$ 的数据，$1 \leq n \leq 20$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq m \leq 3 \times 10^5$。