题目描述

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

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

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

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

数据保证： \(T \le 10^5\)，\(1 \le m \le n \le 10^5\)，\(\sum\limits_{i=1}^{T} m_i \le 10^5\)，\(1 \le x_i \le n\)，\(0 \le y_i \le 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