F. Dora 的颜料

时间限制：3 秒
内存限制：512 MB

可惜，Dora 在画班级壁画时把颜料打翻了。Dora 将壁画视为一个 $n \times n$ 的矩阵 $b$。初始时，对所有 $1 \le i, j \le n$，$b_{i,j} = 0$。

Dora 只有两支不同颜色的刷子。一次操作中，她可以使用其中一支刷子：

• 第一支刷子颜色为 $1$，可以涂满矩阵的一整列。即 Dora 选择 $1 \le j \le n$，并对所有 $1 \le i \le n$ 设置 $b_{i,j} := 1$；
• 第二支刷子颜色为 $2$，可以涂满矩阵的一整行。即 Dora 选择 $1 \le i \le n$，并对所有 $1 \le j \le n$ 设置 $b_{i,j} := 2$。

Dora 会涂色使得最终矩阵 $b$ 只包含 $1$ 和 $2$。

对于矩阵 $b$，记 $f(b)$ 为将初始全 $0$ 矩阵变为 $b$ 所需的最少操作次数。矩阵 $b$ 的美丽值定义为：恰好使用 $f(b)$ 次操作将初始矩阵涂成 $b$ 的不同方式数。如果无法将初始矩阵变为 $b$，则美丽值为 $0$。

然而，Dora 犯了一个均匀随机的错误：你得到的矩阵 $a$ 与真实矩阵 $b$ 恰好有一个元素不同。即存在恰好一个 $(i, j)$，使得 $a_{i,j} = 3 - b_{i,j}$。

请帮助 Dora 计算真实矩阵 $b$ 的期望美丽值，对 $998244353$ 取模（所有 $n^2$ 种可能的错误位置等概率）。

由于矩阵太大，Dora 只会告诉你其中 $m$ 个颜色为 $1$ 的元素的位置，其余 $n^2 - m$ 个元素颜色为 $2$。

---

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$0 \le m \le \min(10^6, n^2)$）—— 矩阵的大小以及颜色为 $1$ 的元素个数。

接下来的 $m$ 行，每行包含两个正整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$），表示 $a_{x_i, y_i} = 1$。

保证若 $i \ne j$，则 $(x_i, y_i) \ne (x_j, y_j)$。

数据保证：所有测试用例的 $n$ 之和不超过 $4 \cdot 10^5$，所有测试用例的 $m$ 之和不超过 $10^6$。

---

输出格式

对于每个测试用例，输出一个整数 —— 真实矩阵 $b$ 的期望美丽值，对 $998244353$ 取模。

---

示例

输入

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
499122178
665496236
120
79859554
776412275
1

---

样例解释

第一个测试用例：矩阵 $a = \begin{bmatrix}1&2\\1&2\end{bmatrix}$。考虑改变元素 $(1,1)$ 来计算答案。

可以证明将初始矩阵涂成 $\begin{bmatrix}2&2\\1&2\end{bmatrix}$ 的最少步数为 $3$。一种涂法：先涂第一行为 $2$，再涂第二列为 $1$，最后涂第二行为 $2$。可以证明这是唯一一种 $3$ 步涂法，因此该矩阵的美丽值为 $1$。类似地，改变其他任意元素得到的矩阵美丽值都是 $1$，所以期望美丽值为 $1$。

第二个测试用例：矩阵 $a = \begin{bmatrix}1&2\\2&2\end{bmatrix}$。考虑改变元素 $(2,2)$ 来计算答案。

可以证明无法将初始矩阵涂成 $\begin{bmatrix}1&2\\2&1\end{bmatrix}$，因此其美丽值为 $0$。改变其他任意元素得到的矩阵美丽值都是 $2$，所以期望美丽值为 $\frac{0+2+2+2}{4} = \frac{6}{4} \equiv 499122178 \pmod{998244353}$。