可悲的是,朵拉在画班级壁画时把油漆倒了。 Dora 将壁画视为大小为 $$$n \times n$$$ 的矩阵 $$$b$$$。最初,对于所有 $$$1 \le i, j \le n$$$,$$$b_{i,j} = 0$$$。
朵拉只有两把画笔,有两种不同的颜色。在一次操作中,她可以使用以下两种画笔之一绘制矩阵:
- 第一个画笔上有颜色 $$$1$$$,可以绘制矩阵的一列。也就是说,Dora 选择 $$$1 \leq j \leq n$$$ 并对所有 $$$1 \leq i \leq n$$$ 做出 $$$b_{i,j} := 1$$$;
- 第二个画笔上有颜色 $$$2$$$,可以绘制矩阵的一行。也就是说,Dora 选择 $$$1 \leq i \leq n$$$ 并对所有 $$$1 \leq j \leq n$$$ 做出 $$$b_{i,j} := 2$$$。
Dora 绘制矩阵,以便生成的矩阵 $$$b$$$ 仅包含 $$$1$$$ 和 $$$2$$$。
对于矩阵 $$$b$$$,让 $$$f(b)$$$ 表示将初始矩阵(仅包含 $$$0$$$)转换为 $$$b$$$ 所需的最少运算次数。矩阵 $$$b$$$ 的美妙之处在于,可以通过精确的 $$$f(b)$$$ 运算来绘制初始矩阵,从而将其转换为 $$$b$$$。如果没有办法把初始矩阵变成$$$b$$$,那么$$$b$$$的美妙之处就是$$$0$$$。
然而,朵拉犯了一个完全随机的错误;给你的矩阵 $$$a$$$ 中只有一个元素与真实矩阵 $$$b$$$ 不同。也就是说,恰好存在一对 $$$(i, j)$$$ 使得 $$$a_{i, j} = 3 - b_{i, j}$$$。
请帮助 Dora 计算真实矩阵 $$$b$$$ 模 $$$998\,244\,353$$$ 的预期美度(所有可能的 $$$n^2$$$ 错误具有相同的概率)。
由于矩阵太大,Dora只会告诉你$$$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\cdot10^5$$$,所有测试用例的$$$m$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出一个整数 - 真实矩阵 $$$b$$$ 的预期美度,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
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
1 499122178 665496236 120 79859554 776412275 1
注意
在第一个测试用例中,矩阵 $$$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]\Righ tarrow\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}$$$。