Dora's Paint
Description
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$.
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$.
For each test case, output a single integer — the expected beauty of the real matrix $b$, modulo $998\,244\,353$.
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$.
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
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}$.