AT_abc321_g [ABC321G] Electric Circuit

有 $N$ 个编号为 $1$ 到 $N$ 的部件和 $M$ 根电缆，打算用它们制作电路。这些部件上共有 $M$ 个红色端子和 $M$ 个蓝色端子，第 $i$ 个红色端子在部件 $R_i$ 上，第 $i$ 个蓝色端子在部件 $B_i$ 上。每根电缆连接一个红色端子和一个蓝色端子。特别地，允许连接同一个部件上的两个端子。同时，一个端子不能连接超过一根电缆。因此，$M$ 根电缆的所有连接方式共有 $M!$ 种（注意电缆之间不区分）。 将部件视为顶点，电缆视为边，把这个电路看作一个图，记其连通分量数为 $s$。从 $M!$ 种电缆连接方式中随机选择一种时，$s$ 的期望值是多少？请将结果对 $998244353$ 取模后输出。 关于对 $998244353$ 取模的期望值 可以证明，所求期望值一定是有理数。在本题的约束下，设其化为最简分数 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R\times Q\equiv P\pmod{998244353}$ 且 $0\leq R

输入从标准输入读入，格式如下： > $N$ $M$ $R_1$ $R_2$ $\dots$ $R_M$ $B_1$ $B_2$ $\dots$ $B_M$

输出 $s$ 的期望值对 $998244353$ 取模后的结果。

## 限制 - $1\leq N\leq 17$ - $1\leq M\leq 10^5$ - $1\leq R_i, B_i\leq N$ - 输入均为整数 ## 样例解释 1 用 $(i, j)$ 表示第 $i$ 个红色端子和第 $j$ 个蓝色端子用电缆连接的情况。 - $(1,1), (2,2)$ 的情况下：形成 $\lbrace 1,3\rbrace$ 和 $\lbrace 2\rbrace$ 两个连通分量，所以 $s=2$。 - $(1,2), (2,1)$ 的情况下：整体为一个连通分量，所以 $s=1$。 因此，$s$ 的期望值为 $\frac{3}{2}\equiv 499122178\pmod{998244353}$。 ## 样例解释 2 无论如何连接，$s=N$。 由 ChatGPT 4.1 翻译