题目描述

A shop sells $N$ items numbered $1, 2, \ldots, N$.

There are $M$ people who visit the shop one after another. When person $i$ arrives, they first look at which items are currently for sale, and then act as follows:

• They buy item $A_i$ if it is available.
• Otherwise, they buy item $B_i$ if it is available.
• Otherwise, they buy nothing and leave.

Note that it is possible that $A_i = B_i$.

There are $M!$ possible arrival orders for the $M$ people. Compute the number of arrival orders for which every person is able to buy an item. Output that number modulo $998244353$.

输入格式

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

The first line contains an integer $N$ ($1 \leq N \leq 200\,000$) representing the number of items sold in the store and $M$ ($1 \leq M \leq N$) representing the number of people visiting the store.

Each of the following $M$ lines contains two integers $A_i$ and $B_i$ ($1 \leq A_i, B_i \leq N$).

输出格式

Print the answer.

4 3
2 1
3 2
3 4

4

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

198