F. Dora's Paint
brute force; combinatorics; constructive algorithms; graphs; implementation
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\).
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}$$$.