Background

MX is studying the properties of permutations. One day, she took out $n$ cards and lined them up, wanting to fill numbers on them to form a permutation of $1\sim n$.

While MX was not paying attention, Piggy secretly wrote numbers on some cards.

Problem Description

MX soon noticed all of this. However, she was not angry. Instead, she thought about an interesting problem: if she fills some numbers so that it is still a permutation, and its longest increasing subsequence has length $n-1$, how many ways are there to fill the numbers?

Piggy is fairly decent. He did not write the same number in different positions.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases.
For each test case:

• The first line contains two integers $n,q$, representing the number of cards and how many numbers Piggy has already filled in.
• The second line contains $2q$ integers. The $(2i-1)$-th and $(2i)$-th integers $(x,y)$ mean that the $x$-th number is filled as $y$ by Piggy.

Output Format

Output $T$ lines, each line containing one integer representing the answer.

2
10 4
2 2 4 8 6 5 7 6
2 0

1
1

2
40 21
1 1 2 2 6 6 7 7 8 8 9 9 10 10 11 11 15 15 16 16 23 23 24 24 25 25 26 26 30 30 34 35 35 36 36 37 37 38 38 39 40 40
40 15
3 3 4 4 14 14 15 15 17 17 19 19 24 23 25 24 27 26 30 29 31 30 33 32 35 34 39 38 40 39

4
4

Hint

Sample Explanation

Use $-1$ to represent that the number at this position has not been determined yet.
Sample $1$: the permutation given in the first test case is $-1,2,-1,8,-1,5,6,-1,-1,-1$. It is easy to see that only $1,2,3,8,4,5,6,7,9,10$ has a longest increasing subsequence length of $10-1=9$. The permutation given in the second test case is $-1,-1$, and $2,1$ is the only sequence that satisfies the requirement.

This problem uses bundled tests.

Constraints: $0\le q\le n$, $1\le n\le 5\times 10^5$, $1\le T\le 10^5$, $1 \le x,y \le n$.

Translated by ChatGPT 5