G1. Учись! (простая версия)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Различия между версиями заключаются в ограничениях на $$$n$$$ и сумму $$$n$$$. В этой версии $$$n \leq 3000$$$, а сумма $$$n$$$ не превосходит $$$10^4$$$. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Так-так-так, посмотрим, как Бесси распоряжается своими финансами. Похоже, она в финансовой яме! К счастью, чтобы решить эту проблему, она устраивается на работу в Moogle. Собеседования в Moogle требуют глубокого знания непонятных алгоритмов и сложных структур данных, но Бесси получила от легендарного гроссмейстера наводку на то, что именно ей нужно изучить.

Бесси написала следующий код для бинарного поиска определенного элемента $$$k$$$ в возможно несортированном массиве $$$[a_1, a_2,\ldots,a_n]$$$ с $$$n$$$ элементами.

let l = 1
let h = n

while l < h:
  let m = floor((l + h) / 2)

  if a[m] < k:
    l = m + 1
  else:
    h = m

return l

Бесси отправила свой код в задачу фермера Джона с $$$m$$$ ($$$1 \leq m \leq n$$$) тестами. $$$i$$$-й тест имеет вид $$$(x_i, k_i)$$$ ($$$1 \leq x, k \leq n$$$). Гарантируется, что все $$$x_i$$$ различны и все $$$k_i$$$ различны.

Тест $$$i$$$ корректен, если выполняются следующие условия:

  1. $$$x_i$$$-й элемент в массиве — $$$k_i$$$.
  2. Если Бесси вызовет двоичный поиск, как показано в коде выше, для $$$k_i$$$, то он вернет $$$x_i$$$.

Возможно, не все $$$m$$$ тестов будут корректны на одном и том же массиве, поэтому фермер Джон удалит некоторые из них, чтобы Бесси могла пройти все тесты. Пусть $$$r$$$ — это минимальное количество тестов, которое нужно удалить, чтобы существовал массив $$$[a_1, a_2,\ldots,a_n]$$$, в котором $$$1 \leq a_i \leq n$$$, чтобы все оставшиеся тесты были корректными.

Помимо нахождения $$$r$$$, фермер Джон хочет, чтобы вы подсчитали количество массивов $$$[a_1, a_2,\ldots,a_n]$$$, в которых $$$1 \leq a_i \leq n$$$, таких, что существует способ удалить ровно $$$r$$$ тестов так, чтобы все оставшиеся тесты были корректными. Поскольку это число может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq m \leq n \leq 3000$$$), обозначающих длину массива и количество тестов.

Следующие $$$m$$$ строк содержат по два целых числа, описывающих тесты. В $$$i$$$-й строке содержится два целых числа $$$x_i$$$ и $$$k_i$$$ ($$$1 \leq x_i, k_i \leq n$$$), обозначающих индекс и значение данного теста. Гарантируется, что все $$$x_i$$$ различны и все $$$k_i$$$ различны.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

Выходные данные

Для каждого набора входных данных выведите два целых числа: $$$r$$$ — минимальное количество удаленных тестов, чтобы существовал массив, в котором все оставшиеся тесты корректны; и количество массивов, для которых можно удалить $$$r$$$ тестов, чтобы все оставшиеся тесты были корректны, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
2
5 4
1 1
2 2
4 3
5 4
5 4
5 4
2 5
1 2
3 3
Выходные данные
0 1
1 3
Входные данные
2
6 6
1 3
2 5
3 1
4 2
5 4
6 6
30 8
19 22
6 12
12 1
28 27
3 4
14 25
29 14
11 15
Выходные данные
3 78
3 839271911
Примечание

Рассмотрим первый пример.

В первом наборе входных данных массив $$$[1,2,2,3,4]$$$ удовлетворяет всем $$$m$$$ тестам, поэтому минимальное количество тестов, которые должна удалить Бесси, равно $$$0$$$. Обратите внимание, что это также единственный массив, который удовлетворяет всем $$$m$$$ тестам.

Во втором наборе входных данных минимальное количество тестов, которое Бесси должна удалить, равняется $$$1$$$. Единственный тест, который Бесси может удалить, это $$$(2,5)$$$. Если Бесси удалит тест $$$(2,5)$$$, то массивами, удовлетворяющими оставшимся $$$m-1$$$ тестам, будут $$$[2,2,3,1,4]$$$, $$$[2,2,3,2,4]$$$, $$$[2,2,3,3,4]$$$.