Description

Arrange seats for $n$ people. First assign each person a number from $1\sim n$. Let the number of the $i$-th person be $a_i$ (different people may share the same number). Then, starting from the first person, everyone takes their seat in order.

When the $i$-th person arrives, they try to sit at seat $a_i$. If $a_i$ is occupied, they try $a_{i+1}$. If $a_{i+1}$ is also occupied, they try $a_{i+2}$, … If they have tried up to the $n$-th and still cannot sit, then the arrangement is invalid.

However, the numbers of $m$ people are already fixed (they may have bribed your boss), and you can only assign numbers for the remaining people. Find how many valid arrangements there are. Since the answer may be large, output it modulo $M$.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains three integers, representing $n,m,M$.

If $m$ is not $0$, the next line contains $m$ pairs of integers $p_1,q_1,p_2,q_2,\ldots,p_m,q_m$, where the $i$-th pair $p_i,q_i$ means that the number of the $p_i$-th person must be $q_i$.

Output Format

For each test case, output one line. If there is a solution, output YES followed by one integer equal to the number of valid arrangements $\bmod\ M$. Note that there is exactly one space between YES and the number. Otherwise, output NO.

2
4 3 10
1 2 2 1 3 1
10 3 8882
7 9 2 9 5 10

YES 4
NO

Hint

Constraints:

• For $30\%$ of the testdata, $1 \le n \le 10$, $1 \le M \le 32767$.
• For $100\%$ of the testdata, $1 \le T \le 10$, $1 \le n \le 300$, $0 \le m \le n$, $2 \le M \le 10^9$, $1 \le p_i,q_i \le n$, and it is guaranteed that the $p_i$ are pairwise distinct.

Translated by ChatGPT 5