说明

一家商店出售 $N$ 件商品，编号为 $1, 2, \ldots, N$。

有 $M$ 个人依次访问这家商店。当第 $i$ 个人到达时，他们会先查看当前有哪些商品在售，然后按以下规则行动：

• 如果商品 $A_i$ 有货，他们就购买商品 $A_i$。
• 否则，如果商品 $B_i$ 有货，他们就购买商品 $B_i$。
• 否则，他们什么也不买就离开。

注意，可能存在 $A_i = B_i$ 的情况。

这 $M$ 个人共有 $M!$ 种可能的到达顺序。请计算有多少种到达顺序使得每个人都能购买到一件商品。输出该数目对 $998244353$ 取模的结果。

输入格式

$$\begin{aligned} & N \ M \\ & A_1 \ B_1 \\ & A_2 \ B_2 \\ & \vdots \\ & A_M \ B_M \end{aligned}$$

第一行包含两个整数 $N$（$1 \leq N \leq 200\,000$）和 $M$（$1 \leq M \leq N$），分别表示商店出售的商品数量和访问商店的人数。

接下来的 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$（$1 \leq A_i, B_i \leq N$）。

输出格式

输出答案。

4 3
2 1
3 2
3 4

4

6 6
2 3
4 3
5 4
2 5
5 1
6 6

198

提示

翻译由 DeepSeek V3.2 完成