F. Dora's Paint
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Sadly, Dora poured the paint when painting the class mural. Dora considers the mural as the matrix $$$b$$$ of size $$$n \times n$$$. Initially, $$$b_{i,j} = 0$$$ for all $$$1 \le i, j \le n$$$.

Dora has only two brushes which have two different colors. In one operation, she can paint the matrix with one of two brushes:

  • The first brush has color $$$1$$$ on it and can paint one column of the matrix. That is, Dora chooses $$$1 \leq j \leq n$$$ and makes $$$b_{i,j} := 1$$$ for all $$$1 \leq i \leq n$$$;
  • The second brush has color $$$2$$$ on it and can paint one row of the matrix. That is, Dora chooses $$$1 \leq i \leq n$$$ and makes $$$b_{i,j} := 2$$$ for all $$$1 \leq j \leq n$$$.

Dora paints the matrix so that the resulting matrix $$$b$$$ contains only $$$1$$$ and $$$2$$$.

For a matrix $$$b$$$, let $$$f(b)$$$ denote the minimum number of operations needed to turn the initial matrix (containing only $$$0$$$) into $$$b$$$. The beauty of a matrix $$$b$$$ is the number of ways to paint the initial matrix in exactly $$$f(b)$$$ operations to turn it into $$$b$$$. If there's no way to turn the initial matrix into $$$b$$$, the beauty of $$$b$$$ is $$$0$$$.

However, Dora made a uniformly random mistake; there's exactly one element different in the matrix $$$a$$$ given to you from the real matrix $$$b$$$. That is, there is exactly one pair $$$(i, j)$$$ such that $$$a_{i, j} = 3 - b_{i, j}$$$.

Please help Dora compute the expected beauty of the real matrix $$$b$$$ modulo $$$998\,244\,353$$$ (all possible $$$n^2$$$ mistakes have equal probability).

Since the size of the matrix is too large, Dora will only tell you the positions of $$$m$$$ elements of color $$$1$$$, and the remaining $$$n^2-m$$$ elements have color $$$2$$$.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq m \leq \min(10^6, n^2)$$$) — the size of the matrix and the number of elements of color $$$1$$$.

Then $$$m$$$ lines follow, each containing two positive integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) — denoting that $$$a_{x_i, y_i} = 1$$$.

It is guaranteed that if $$$i \neq j$$$, then $$$(x_i, y_i) \neq (x_j, y_j)$$$.

It is also guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4\cdot10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer — the expected beauty of the real matrix $$$b$$$, modulo $$$998\,244\,353$$$.

Example
Input
7
2 2
1 1
1 2
2 1
1 1
3 2
1 1
3 3
6 0
5 10
1 1
1 2
1 3
2 1
2 3
5 1
5 2
5 3
5 4
5 5
3 5
1 1
1 3
2 2
3 1
3 3
4 3
1 1
2 3
2 4
Output
1
499122178
665496236
120
79859554
776412275
1
Note

In the first test case, the matrix $$$a = \left[\begin{matrix}1&1\\2&2\end{matrix}\right]$$$. Let's consider changing the element $$$(1,1)$$$ to calculate the answer.

It can be proved that the minimum steps to paint the initial matrix into $$$\left[\begin{matrix}2&1\\2&2\end{matrix}\right]$$$ is $$$3$$$. We can first paint the first row into color $$$2$$$, then paint the second column into color $$$1$$$, and finally paint the second row into color $$$2$$$. The process is listed below:

$$$$$$\left[\begin{matrix}0&0\\0&0\end{matrix}\right]\Rightarrow\left[\begin{matrix}2&2\\0&0\end{matrix}\right]\Rightarrow\left[\begin{matrix}2&1\\0&1\end{matrix}\right]\Rightarrow\left[\begin{matrix}2&1\\2&2\end{matrix}\right]$$$$$$

It can be proved that this is the only way to paint the matrix in $$$3$$$ steps. So the beauty of the matrix $$$\left[\begin{matrix}2&1\\2&2\end{matrix}\right]$$$ is $$$1$$$. Similarly, if any other element of the matrix is changed, the beauty is always $$$1$$$, so the expected beauty of the real matrix $$$b$$$ is $$$1$$$.

In the second test case, the matrix $$$a = \left[\begin{matrix}1&2\\2&2\end{matrix}\right]$$$. Let's consider changing the element $$$(2, 2)$$$ to calculate the answer.

It can be proven that it's impossible to paint the initial matrix into $$$\left[\begin{matrix}1&2\\2&1\end{matrix}\right]$$$, so its beauty is $$$0$$$. If any other element of the matrix is changed, the beauty is always $$$2$$$, so the expected beauty is $$$\frac{0 + 2 + 2 + 2}{4} = \frac{6}{4} \equiv 499\,122\,178 \pmod {998\,244\,353}$$$.