CF2006F Dora's Paint

不幸的是，朵拉在绘制班级壁画时颜料洒了。她将壁画视作一个 $n \times n$ 的矩阵 $b$，最开始时，矩阵中所有元素 $b_{i,j}$ 都是 0。 朵拉有两支不同颜色的画笔，在一次操作中，她可以使用其中一支画笔来为矩阵上色： - 第一支画笔的颜色为 1，可以为矩阵中的某一列上色。具体来说，朵拉选择某一列 $1 \leq j \leq n$，然后将这一列中所有的元素设置为 1，即 $b_{i,j} := 1$ 对于所有 $1 \leq i \leq n$； - 第二支画笔的颜色为 2，可以为矩阵中的某一行上色。具体来说，朵拉选择某一行 $1 \leq i \leq n$，然后将这一行中所有的元素设置为 2，即 $b_{i,j} := 2$ 对于所有 $1 \leq j \leq n$。 朵拉需要最终让整个矩阵 $b$ 只包含颜色 1 和颜色 2。 对于任意矩阵 $b$，定义 $f(b)$ 为从初始全 0 矩阵经过最少操作次数变为矩阵 $b$ 所需的最小步骤数。矩阵 $b$ 的“美丽值”是指用恰好 $f(b)$ 次操作将初始矩阵变为 $b$ 的不同方法数。如果不能将初始矩阵变为 $b$，那么美丽值为 0。 然而，朵拉随手犯了一个错误；实际的矩阵 $a$ 和真正应该得到的矩阵 $b$ 仅有一个元素不同。换句话说，存在一个唯一的元素位置 $(i, j)$，使得 $a_{i,j} = 3 - b_{i,j}$。 请帮助朵拉计算在所有可能错误的情况下，真实矩阵 $b$ 的期望美丽值，并对结果取模 $998\,244\,353$。 由于矩阵比较大，朵拉只告诉我们 $m$ 个颜色为 1 的元素的位置，剩下的 $n^2 - m$ 个元素的颜色为 2。

每个测试点有多个测试用例。第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$)，表示测试用例的数量。接下来是每个测试用例的具体内容。 对于每个测试用例的第一行，输入两个整数 $n$ 和 $m$ ($2 \leq n \leq 2 \cdot 10^5$, $0 \leq m \leq \min(10^6, n^2)$)，表示矩阵的大小以及颜色为 1 的元素数量。 接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($1 \leq x_i, y_i \leq n$)，表示矩阵 $a$ 中位置 $(x_i, y_i)$ 的元素是颜色 1。 确保当 $i \neq j$ 时，$(x_i, y_i) \neq (x_j, y_j)$。 保证所有测试用例中 $n$ 的总和不超过 $4 \cdot 10^5$，$m$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数——这个整数是对真实矩阵 $b$ 的期望美丽值取模 $998\,244\,353$ 的结果。

在第一个测试用例中，矩阵 $a = \left[\begin{matrix}1&1\\2&2\end{matrix}\right]$。考虑将元素 $(1,1)$ 改变以计算答案。 可以证明，将初始矩阵变为 $\left[\begin{matrix}2&1\\2&2\end{matrix}\right]$ 需要至少 3 步。具体方法是，先将第一行涂成颜色 2，然后将第二列涂成颜色 1，最后将第二行涂成颜色 2。操作过程如下： $$ \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] $$ 事实证明，这种方法是唯一可以用3步实现的方法。因此，矩阵 $\left[\begin{matrix}2&1\\2&2\end{matrix}\right]$ 的美丽值为 1。类似地，如果改变矩阵中的其他元素，美丽值仍然是 1，所以真实矩阵 $b$ 的期望美丽值为 1。 在第二个测试用例中，矩阵 $a = \left[\begin{matrix}1&2\\2&2\end{matrix}\right]$。考虑将元素 $(2, 2)$ 改变以计算答案。 可以证明无法将初始矩阵变为 $\left[\begin{matrix}1&2\\2&1\end{matrix}\right]$，因此其美丽值是 0。如果改变矩阵中的其他任何元素，美丽值总是 2，所以期望美丽值为 $\frac{0 + 2 + 2 + 2}{4} = \frac{6}{4} \equiv 499\,122\,178 \pmod {998\,244\,353}$。 **本翻译由 AI 自动生成**