English Class

Bru received a matching problem in English class, in the form shown below.

The matching problem is solved with $N$ points on the left and $N$ points on the right, arranged vertically. More precisely, you may assume that for every integer $i$ with $1 \le i \le N$, there is one point at $(1, i)$ and one point at $(2, i)$ on the coordinate plane.

Each point has a label next to it. The label next to $(1, i)$ is a word, and the label next to $(2, i)$ is its meaning, both in English. Connect two points with a segment when the word and the meaning match. A correct solution makes every point an endpoint of exactly one segment, and every segment has one endpoint with x-coordinate $1$ and the other with x-coordinate $2$.

Bru tried hard but found only $K$ of the $N$ segments. He connected the remaining points so that the result is a correct answer.

While deciding how to connect the remaining points, Bru wanted the final answer to be a beautiful answer.

A correct answer is an answer that satisfies both conditions below.

• Every segment has endpoints $(1, i)$ and $(2, j)$ for some $1 \le i, j \le N$ (where $i$ and $j$ are integers).
• All $2N$ points are endpoints of exactly one segment.

The figures below show correct and incorrect answers.

Correct answer	Incorrect answer	Incorrect answer

A beautiful answer is a correct answer that also satisfies both conditions below.

• No three or more segments meet at one point.
• There is no closed region enclosed by the segments. In other words, using only parts of the given segments, you cannot form a polygon with positive area.

The figures below show beautiful and non-beautiful answers.

Beautiful answer	Not a beautiful answer	Not a beautiful answer

Bru wants to count the beautiful answers he can build by connecting the remaining points while keeping the segments he has already drawn fixed.

The first line contains two integers $N$ and $K$.

Each of the next $K$ lines contains two integers $U_i$ and $V_i$, separated by a space. This means that $(1, U_i)$ and $(2, V_i)$ are connected by a segment.

Print the number of correct answers that can be made by connecting the remaining points, modulo $998\ 244\ 353$.

• $3 \le N \le 2 \times 10^5$
• $0 \le K \le N$
• $1 \le U_i \le N$ ($1 \le i \le K$)
• $1 \le V_i \le N$ ($1 \le i \le K$)
• $U_i \neq U_j$ ($1 \le i < j \le K$)
• $V_i \neq V_j$ ($1 \le i < j \le K$)