AT_utpc2022_e.Parallel Swapping

有两个长度为 $N$ 的排列 $P=(P_1,P_2,\ldots,P_N),\ Q=(Q_1,Q_2,\ldots,Q_N)$。一开始 $P_i = Q_i = i$（$1 \leq i \leq N$）。对于这两个排列，可以执行如下的操作，次数不限（可以为零次）：

• 选择一个整数 $i$，满足 $1 \le i \le M$。将 $P$ 的第 $a_i$ 位和第 $b_i$ 位的元素交换，同时将 $Q$ 的第 $c_i$ 位和第 $d_i$ 位的元素交换。

请你求出，可以通过若干次操作后得到的 $(P, Q)$ 状态的不同组数，并对 $998244353$ 取模。

输入按如下格式从标准输入读入：

$N$ $M$
$a_1$ $b_1$ $c_1$ $d_1$
$\vdots$
$a_M$ $b_M$ $c_M$ $d_M$

输出答案，表示可能的不同 $(P, Q)$ 状态的组数，对 $998244353$ 取模。

样例解释 1

可能得到的 $(P, Q)$ 状态为 $P=(1, 2, 3),\ Q=(1, 2, 3)$ 和 $P=(2, 1, 3),\ Q=(1, 3, 2)$，共计 2 种。

数据范围

• 输入均为整数。
• $2 \leq N \leq 5000$
• $0 \leq M \leq 5000$
• $1 \le a_i, b_i, c_i, d_i \le N$
• $a_i < b_i$
• $c_i < d_i$
• 若 $i \neq j$，则 $(a_i, b_i, c_i, d_i) \neq (a_j, b_j, c_j, d_j)$

由 ChatGPT 5 翻译