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 翻译