CF2006F Dora's Paint

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}$$$.