F. Краски Доры
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

К сожалению, Дора пролила краску, когда рисовала мурал в классе. Дора рассматривает мурал как матрицу $$$b$$$ размера $$$n \times n$$$. Изначально $$$b_{i,j} = 0$$$ для всех $$$1 \le i, j \le n$$$.

У Доры есть только две кисти, которые имеют два разных цвета. За одну операцию она может покрасить матрицу одной из двух кистей:

  • Первая кисть имеет цвет $$$1$$$ и может покрасить один столбец матрицы. То есть, Дора выбирает целое число $$$1 \leq j \leq n$$$ и присваивает $$$b_{i,j} := 1$$$ для всех $$$1 \leq i \leq n$$$;
  • Вторая кисть имеет цвет $$$2$$$ и может покрасить одну строку матрицы. То есть, Дора выбирает целое число $$$1 \leq i \leq n$$$ и присваивает $$$b_{i,j} := 2$$$ для всех $$$1 \leq j \leq n$$$.

Дора раскрашивает матрицу так, чтобы полученная матрица $$$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}$$$.

Пожалуйста, помогите Доре вычислить ожидаемую красоту настоящей матрицы $$$b$$$ по модулю $$$998\,244\,353$$$ (все возможные $$$n^2$$$ ошибок имеют равную вероятность).

Поскольку размер матрицы слишком велик, Дора скажет вам только позиции $$$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$$$.

Пример
Входные данные
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 = \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}$$$.