← 返回题目列表

AtCoder · codequeen2025_final_f

F. 亚克力支架

中文机器翻译题面 查看原题

配点 : 500 点

問題文

高桥是偶像团体Bit♡Beat的粉丝,也是成员。 N 适合所有人的亚克力支架 1 我各有一个。

高桥君 我正在尝试将 N 亚克力支架排成一排,但我正在尝试 2 我们认为人们不应该相邻放置。具体来说, 对于 i=1,2,\ldots,M 反对 A_i 与第 名成员 B_i 我想安排第三位成员的亚克力支架,使它们不彼此相邻。

高桥的 M 满足所有个人需求 N 亚克力支架有多少种排列方式? 除以 998244353 后求余数。

制約

  • 2\le N\le 10^6
  • 0\le M\le 16
  • 1\le A_i < B_i \le N
  • (A_i , B_i) \neq (A_j , B_j) (i \neq j)
  • 所有输入值均为整数

入力

输入将以以下格式从标准输入给出。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

打印答案。


入力例 1

3 1
1 2

出力例 1

2

下面 2 两个排列满足条件。

  • 2 第会员, 3 第会员, 1 与成员的亚克力支架按顺序排列。
  • 1 第会员, 3 第会员, 2 与成员的亚克力支架按顺序排列。

因此, 请输出 2 。


入力例 2

5 4
1 4
1 2
1 5
1 3

出力例 2

0

没有满足条件的排序方法。因此, 请打印除以 0 。


入力例 3

15 5
3 8
8 9
8 12
4 9
4 7

出力例 3

720555423

998244353 后的余数。