問題一覧 > 通常問題

No.1116 Cycles of Dense Graph

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 29
作問者 : 37zigen37zigen / テスター : hotmanwwhotmanww
7 ProblemId : 4557 / 出題時の順位表
問題文最終更新日: 2020-07-18 18:21:17

問題文

各頂点に $1,\ldots,N$ のラベルが付いた $N$ 頂点完全グラフ $G$ がある。
グラフ $G$ から $M$ 辺 $\{a_i,b_i\}\ (1 \leq i \leq M)$ を取り除いた部分グラフにおけるサイクルの数を $998244353$ で割った余りを求めよ。

サイクルとは、次のように与えられるグラフ $(V,E)$ のことである。 $$ \begin{align} &V=\{x_0,\ldots,x_k\}\\ &E=\{x_0x_1,x_1x_2,\ldots,x_{k-1}x_k,x_kx_0\} \end{align} $$ ここで、$k \geq 2$ かつ $x_i$ はすべて異なるものとする。

入力

$N\ M$
$a_1\ b_2$
$\vdots$
$a_M\ b_M$

$1 \leq N \leq 10^5$
$0 \leq M \leq \min(N(N-1)/2,15)$
$1 \leq a_i,b_i \leq N$
$a_i \neq b_i$
$\{a_i , b_i\} \neq \{a_j, b_j\} \ (i\neq j)$

出力

最後に改行してください。

サンプル

サンプル1
入力
3 1
1 2
出力
0

サンプル2
入力
4 0
出力
7

$K_4$ に含まれるサイクルは次の7つ。

サンプル3
入力
6 5
1 3
2 4
3 5
4 1
5 2
出力
21

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。