Go Learn! (Easy Version)
Contest: Codeforces Global Round 27
Difficulty rating: 3300
Tags: dp, trees

The differences between the easy and hard versions are the constraints on $$$n$$$ and the sum of $$$n$$$. In this version, $$$n \leq 3000$$$ and the sum of $$$n$$$ does not exceed $$$10^4$$$. You can only make hacks if both versions are solved.

Well, well, well, let's see how Bessie is managing her finances. She seems to be in the trenches! Fortunately, she is applying for a job at Moogle to resolve this issue. Moogle interviews require intensive knowledge of obscure algorithms and complex data structures, but Bessie received a tip-off from an LGM on exactly what she has to go learn.

Bessie wrote the following code to binary search for a certain element $$$k$$$ in a possibly unsorted array $$$[a_1, a_2,\ldots,a_n]$$$ with $$$n$$$ elements.

Bessie submitted her code to Farmer John's problem with $$$m$$$ ($$$1 \leq m \leq n$$$) tests. The $$$i$$$-th test is of the form $$$(x_i, k_i)$$$ ($$$1 \leq x, k \leq n$$$). It is guaranteed all the $$$x_i$$$ are distinct and all the $$$k_i$$$ are distinct.

Test $$$i$$$ is correct if the following hold:

1. The $$$x_i$$$-th element in the array is $$$k_i$$$.
2. If Bessie calls the binary search as shown in the above code for $$$k_i$$$, it will return $$$x_i$$$.

It might not be possible for all $$$m$$$ tests to be correct on the same array, so Farmer John will remove some of them so Bessie can AC. Let $$$r$$$ be the minimum of tests removed so that there exists an array $$$[a_1, a_2,\ldots,a_n]$$$ with $$$1 \leq a_i \leq n$$$ so that all remaining tests are correct.

In addition to finding $$$r$$$, Farmer John wants you to count the number of arrays $$$[a_1, a_2,\ldots,a_n]$$$ with $$$1 \leq a_i \leq n$$$ such that there exists a way to remove exactly $$$r$$$ tests so that all the remaining tests are correct. Since this number may be very large, please find it modulo $$$998\,244\,353$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 3000$$$) denoting the number of the array and the number of tests.

The following $$$m$$$ lines each contain two integers, describing the tests. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$k_i$$$ ($$$1 \leq x_i, k_i \leq n$$$) denoting the index and value of the test. It is guaranteed all $$$x_i$$$ are distinct and all $$$k_i$$$ are distinct.

It is guaranteed the sum of $$$n$$$ across all test cases does not exceed $$$10^4$$$.

Output format:
For each test case, output two integers, $$$r$$$ — the minimum of tests removed so that there exists an array so that all remaining tests are correct, and the number of arrays such that it is possible to remove $$$r$$$ tests to make all remaining tests correct modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
Consider the first example.

In the first test case, the array $$$[1,2,2,3,4]$$$ satisfies all $$$m$$$ tests, so the minimum number of tests Bessie has to remove is $$$0$$$. Note that this is also the only array that satisfies all $$$m$$$ tests.

In the second test case, the minimum number of tests Bessie has to remove is $$$1$$$. The only test Bessie can remove is $$$(2,5)$$$. If Bessie removes test $$$(2,5)$$$, then the arrays satisfying the remaining $$$m-1$$$ tests are $$$[2,2,3,1,4]$$$, $$$[2,2,3,2,4]$$$, $$$[2,2,3,3,4]$$$.

Example input:
2
5 4
1 1
2 2
4 3
5 4
5 4
5 4
2 5
1 2
3 3

Example output:
0 1
1 3

Example input:
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

Example output:
3 78
3 839271911

Editorial:
Let's sort the tests by $$$x_i$$$. I claim a subsequence of tests $$$t_1 \dots t_r$$$ remaining is correct iff
1. $$$k_{t_i} < k_{t_{i+1}}$$$ for all $$$1 \leq i < r$$$.
2. $$$x_{t_1} = 1$$$ or $$$k_{t_1} \neq 1$$$.
In other words, the set of tests is increasing, and if some test has $$$k_i = 1$$$, that test's $$$x_i$$$ must $$$= 1$$$. This is because a binary search for value $$$1$$$ will always be index $$$1$$$. Otherwise, the array $$$a$$$ where $$$a_i = k_{t_j}$$$ if $$$i = t_j$$$ for some $$$j$$$, $$$a_i = 1$$$ if $$$i < x_{t_1}$$$ or $$$a_i = a_{i-1}$$$ is a valid array for all of these tests. This is because the binary search will perform normally and correctly lower bound all of those occurrences.
Suppose then the tests were not increasing. Consider two indices $$$i$$$ and $$$j$$$ such that $$$x_i < x_j$$$ but $$$k_i > k_j$$$. Consider the $$$l$$$, $$$r$$$, and $$$m$$$ in the binary search where $$$l \leq x_i \leq m$$$ and $$$m+1 \leq x_j \leq r$$$. For test $$$i$$$ to search left, $$$a_m$$$ must be $$$\geq k_i$$$, but $$$j$$$ also had to search right so $$$a_m$$$ must be $$$ < k_j$$$. Then we need $$$k_i \leq a_m < k_j$$$, but we assumed that $$$k_i > k_j$$$, hence a contradiction. $$$\Box$$$
Suppose $$$r$$$ was the minimum number of tests removed. I claim for each valid $$$a_1 \dots a_n$$$, there is exactly one set of $$$r$$$ tests to remove to make $$$a_1 \dots a_n$$$ valid. This is because if there were more than one way, these two choices of the $$$m-r$$$ tests to keep would be different. Then $$$a$$$ would actually satisfy at least $$$m-r+1$$$ remaining tests, so $$$r$$$ is not minimal.
Putting these two statements together, we can formulate an $$$O(m^2 \log n)$$$ dp.
Let $$$\text{touch}(i)$$$ denote the set of indices $$$m$$$ such that a binary search that terminates at position $$$i$$$ checks all these $$$a_m$$$ at some point. Also, let $$$k_i$$$ be the $$$k$$$ of the test with $$$x = i$$$. If no such test exists $$$k_i$$$ is undefined.
Let $$$\text{dp}_i$$$ be a tuple of $$$(x, y)$$$ where $$$x$$$ is the longest increasing set of tests where the last test has $$$x_j = i$$$ and $$$y$$$ is the number of ways to fill the prefix of $$$a_1 \dots a_{i}$$$ to satisfy some choice of $$$x$$$ tests removed. Note that $$$\text{dp}_i$$$ is not defined when there does not exist some $$$x_j = i$$$. Also if, $$$i \neq 1$$$, and $$$k_i = 1$$$, $$$\text{dp}_i = (0, 0)$$$.
Consider computing some $$$\text{dp}_i$$$. Let $$$mx = \max\limits_{j < i, k_j < k_i} \text{dp}_j.x$$$. $$$\text{dp}_i = (mx+1, \sum\limits_{j < i, k_j < k_i, \text{dp}_j.x = mx} cnt(j, i)\cdot \text{dp}_j.y)$$$ where $$$\text{cnt}(j, i)$$$ is the number of ways to fill the $$$a_i \dots a_j$$$ if both the test with $$$x = i$$$ and the test with $$$x = j$$$ are taken.
Most of the elements between $$$i$$$ and $$$j$$$ will be free, so we can assign them to any number from $$$1 \dots n$$$. Let's determine which (and how many) numbers are not free. Consider all elements $$$m$$$ such that $$$m\in\text{touch}(i)$$$, $$$m\in\text{touch}(j)$$$, and $$$i < m < j$$$. Let there be $$$b$$$ of such $$$m$$$, these elements are forced to take on values $$$k_j \leq v < k_i$$$. Then consider all elements $$$m$$$ such that $$$m \in \text{touch}(i)$$$, $$$m \notin \text{touch}(j)$$$, and $$$i < m < j$$$. Let there be $$$g$$$ such $$$m$$$, these elements are forced to take on values $$$k_j \leq v$$$. Finally, consider all $$$m$$$ such that $$$m \in \text{touch}(j)$$$, $$$m \notin \text{touch}(i)$$$, and $$$i < m < j$$$. Let there be $$$l$$$ such $$$m$$$, these elements are forced to take on values $$$v < k_i$$$. Then $$$\text{cnt}(i, j) = n^{i - j - 1 - (g + m + l)} (k_i - k_j)^b (n - k_j + 1)^g (k_i - 1)^l$$$.
After we have found all the $$$\text{dp}$$$'s, we can try each $$$\text{dp}$$$ as the last test taken in the entire set. We can determine all the elements in the suffix that have their value forced (relative to $$$i$$$).
We can precompute $$$\text{touch}(i)$$$ or compute it on the fly in $$$O(\log n)$$$ time per $$$i$$$. We can also choose to use binpow/precompute powers. As we have $$$m$$$ states with up to $$$m$$$ transitions each each taking $$$O(\log n)$$$ time, our final complexity is $$$O(m^2 \log n)$$$.