P15770 [JAG 2025 Summer Camp #2] To All Tha Customers

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.