Dora's Paint
Contest: Codeforces Round 969 (Div. 1)
Difficulty rating: 3500
Tags: 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$$$.

Input format:
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 format:
For each test case, output a single integer — the expected beauty of the real matrix $$$b$$$, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

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

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

Example output:
1
499122178
665496236
120
79859554
776412275
1

Editorial:
Read the hints.
From the hints, you may understand that, when given the degrees of each node, you can get the initial beauty of a matrix in $$$\mathcal O(n)$$$. To quickly perform topological sort, you should use addition tags to maintain the degrees of each node. Also, this is equal to sorting them by degrees.
Brute-force traversal of each edge solves in $$$\mathcal O(n^3)$$$. First, let's try to solve the problem in $$$\mathcal O(n^2)$$$.
In the Case of Initial Beauty is not $$$0$$$
For an inverted edge between column $$$i$$$ and row $$$j$$$, we claim that the beauty is still not $$$0$$$ if and only if column $$$i$$$ and row $$$j$$$ are in adjacent layers in the initial topological sort.
If they are not in adjacent layers, WLOG let the initial direction be $$$i \to j$$$. Since it's a bipartite graph, we can't get $$$i \to x \to j$$$, but we can definitely get $$$i \to x \to y \to j$$$. If the edge is inverted, then there exists a cycle: $$$i \to x \to y \to j \to i$$$, which means that the beauty becomes $$$0$$$. Otherwise, it can also be proved that no new cycle is created.
Since the answer is $$$\displaystyle\prod_{i=1}^n [\sum_{j=1}^n \text{ColOutdeg}(j) = i]! \cdot \prod_{i=1}^n [\sum_{j=1}^n \text{RowOutdeg}(j) = i]!$$$, a modification will only lead to changes in $$$\mathcal O(1)$$$ terms, and can therefore be easily calculated.
In the Case of Initial Beauty is $$$0$$$
Note that this is a full bipartite graph. This means, if there is a cycle, then there must be a cycle of exactly $$$4$$$ vertices.
Proof:
If we can find the cycle of any number of vertices, we can get a cycle of $$$4$$$ vertices, and after that we can simply try to invert only the $$$4$$$ edges and sum the answer up, otherwise the cycle still exists. The problem is turned down to how to find a cycle.
We can try to DFS from each vertex. If a cycle is found, it will contain no more than $$$2m$$$ edges, and we can do as the proof does to reduce the number of edges (so that the size eventually becomes $$$4$$$).
$$$\rule{1000px}{1px}$$$
Then, let's move on to $$$\mathcal O(n + m)$$$ (In fact, $$$\mathcal O((n + m)\log n)$$$ solutions may pass as well).
In the Case of Initial Beauty is not $$$0$$$
Let's assume that all the blocks are from being $$$\tt 2$$$ to being $$$\tt 1$$$, and then you can calculate the answer efficiently enough. Then, brute go over the $$$\tt 1$$$ blocks and recalculate its contribution to the answer.
In the Case of Initial Beauty is $$$0$$$
Since the topo sorting is done halfway (some nodes are first extracted as previous "layers"), we need to flip an edge to continue. At the moment, however, no remaining vertices have an indegree of $$$0$$$. Then, after a flip, there should be a vertex with an indegree of $$$0$$$ (otherwise the beauty remains $$$0$$$ and we skip it). From this point of view, if there is no vertex with an indegree of $$$1$$$, then the beauty will always be $$$0$$$ after one flip.
If there is a node with an indegree of $$$1$$$ (assume that it is $$$u$$$), we can easily find a cycle of $$$4$$$ vertices containing $$$u$$$:
• We find the only node $$$x$$$ satisfying $$$x \to u$$$.
• We find a node $$$y$$$ satisfying $$$y \to x$$$.
• We find a node $$$z$$$, again, satisfying $$$z \to y$$$.
• There must be $$$u \to z$$$ since the indegree of $$$u$$$ is only $$$1$$$.
There are some other ways to find the cycle. For example, you are just going to find a
pattern, and after selecting a node, you can do sweepline on all the $$$m$$$ occurrences of $$$\tt 1$$$. If you implement it well, it is also in linear time.
Time complexity: $$$\mathcal O(n + m)$$$.