AT_codequeen2025_final_f アクリルスタンド

高桥君是偶像团体 Bit♡Beat 的粉丝，他拥有所有 $N$ 位成员每人一个的亚克力立牌。 现在，高桥君想要将这 $N$ 个亚克力立牌排成一行。但是，他不希望某些特定的 $2$ 位成员的亚克力立牌相邻摆放。具体来说，对于 $i=1,2,\ldots,M$，高桥君要求第 $A_i$ 位成员和第 $B_i$ 位成员的亚克力立牌不能相邻。 请计算有多少种排列方式能够满足高桥君的这 $M$ 个要求，并将答案对 $998244353$ 取模后输出。

输入以如下格式通过标准输入给出。 > $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

请输出满足条件的排列方式数，结果对 $998244353$ 取模。

### 样例解释 1 以下 $2$ 种排列方式满足条件。 - 先排第 $2$ 位成员、再第 $3$ 位成员、再第 $1$ 位成员的亚克力立牌。 - 先排第 $1$ 位成员、再第 $3$ 位成员、再第 $2$ 位成员的亚克力立牌。 因此，应输出 $2$。 ### 样例解释 2 不存在满足条件的排列方式。因此，应输出 $0$。 ### 样例解释 3 请输出对 $998244353$ 取模的结果。 ### 数据范围 - $2 \leq N \leq 10^6$ - $0 \leq M \leq 16$ - $1 \leq A_i < B_i \leq N$ - $(A_i , B_i) \neq (A_j , B_j)$（$i \neq j$） - 输入的所有数均为整数。 由 ChatGPT 5 翻译