题目描述

歪歪小朋友不喜欢计数，但她很喜欢 MEX 。

歪歪首先给出了本题中 排列 的定义：对于一个长度为 $n$ 的序列 $P$，若其中的数字 $p_i$ 都在 $[0,n-1]$ 的范围内，并且每个数字都只出现一次，我们称其为 排列。如 $[1,4,2,3,0]$ 就是一个长度为 $5$ 的排列。

她再定义了函数 $MEX_P[l,r]$ ：在长度为 $n$ 的排列 $P$ 中，有 $1\leq l \leq r \leq n$，其中 $[a_l,a_{l+1}...a_r]$ 组成的子数组中未出现的最小非负整数值即为 $MEX_P[l,r]$。如排列 $P$ 为 $[2,4,3,1,0]$，$l=3,r=5$，组成的子数组为 $[3,1,0]$，未出现的最小非负整数值即为 $2$，故 $MEX_P[3,5]=2$，

歪歪小朋友有一个长度为 $n$ 的排列 $A$，还有一个长度为 $n$ 的 $B$ 序列，其中对于 $1\leq i \leq n$ 都有 $b_i=MEX_A[i,n]$，如果要通过给出排列 $A$ 的来求序列 $B$ 是什么，歪歪小朋友觉得这太简单了，她马上就会了。但是如果给出序列 $B$ 来求 $A$ 呢？歪歪会告诉你序列 $B$ 中 $m$ 项的值，即从形式上来说会给出 $m$ 对 $[x_i,y_i]$，表示 $b_{x_i}=y_i$，很显然，满足条件的排列 $A$ 可能有很多种，或者一种都没有，她想让你告诉他有多少种排列 $A$ 满足条件。答案可能很大，输出对 $998244353$ 取模之后的值。

数据保证：$T\leq10^5$，$1\leq m\leq n\leq10^5$，$\sum\limits_{i=1}^{T} m_i \leq10^5$，$1\leq x_i\leq n$，$0\leq y_i\leq n$，在同一组数据中的 $x_i$ 都是两两不同的。

注意：本题没有对 $n$ 的总和作出限制！

输入格式

第一行输入数据组数 $T$， 对于每一组数据，第一行会输入两个整数 $n,m$，分别表示排列 $A$ 的长度和歪歪告诉你序列 $B$ 的项数。 接下来 $m$ 行，每行输入两个整数 $x_i,y_i$ 表示 $b_{x_i}=y_i$，

输出格式

输出满足条件的排列 $A$ 的种类数。答案对 $998244353$ 取模。

3
4 2
1 4
3 0
6 4
2 4
3 5
5 0
6 0
5 2
1 5
5 0

12
0
96