『XYGOI round1』一些数

MX 在研究排列所具有的性质。这一天，她拿出了 $n$ 张卡片排成一排，想要在上面填数以写成一个 $1\sim n$ 的排列。 Piggy 趁 MX 不注意，偷偷在一些卡片上写了数。

MX 很快发现了这一切。不过她并不生气，而是考虑一个有趣的问题：如果我在上面填一些数，让它依然构成一个排列，且它的最长上升子序列长度为 $n-1$，MX 有多少种填数方法呢？ Piggy 比较良心。他没有在不同的位置上填相同的数。

本题有多组测试数据。 第一行一个整数 $T$ 代表数据组数。 对于每组数据： - 第一行两个整数 $n,q$ 代表卡牌个数和 Piggy 已经填上了多少个数。 - 第二行 $2q$ 个整数，第 $2i-1,2i$ 个整数 $(x,y)$ 代表第 $x$ 个数被 Piggy 填成了 $y$。

输出 $T$ 行，每行一个整数代表答案。

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

#### 样例解释 用 $-1$ 代表此位置数字还未确定。 样例 $1$：第一组给定的排列为 $-1,2,-1,8,-1,5,6,-1,-1,-1$。容易发现，只有 $1,2,3,8,4,5,6,7,9,10$ 的最长上升子序列长度为 $10-1=9$。第二组给定的排列为 $-1,-1$，$2,1$ 为唯一满足要求的序列。 **本题采用捆绑测试。** | Subtask | $\sum n$ | $\sum q$ | 分值 | |:-:|:-:|:-:|:-:| |0|$\le 10$|$\le 10$|10| |1|$\le 15$|$\le 10$|20| |2|$\le 5\times 10^3$|$\le 5\times 10^3$|30| |3|$\le 5\times 10^5$|$\le 5\times 10^5$|40| 保证 $ 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$。