Description

Arrange seats for $n$ people. First, assign each person a label in $1\thicksim n$. Let the label of the $i$-th person be $a_i$ (different people may share the same label).

Then, starting from the first person, they take seats in order. When the $i$-th person arrives, they try to sit at $a_i$. If $a_i$ is occupied, they try $a_i+1$. If $a_i+1$ is also occupied, they try $a_i+2$, and so on. If all attempts up to seat $n$ fail, the arrangement is invalid.

However, the labels of $m$ people have already been fixed (they may have bribed your boss...), and you can only assign labels to the remaining people. Find the number of valid assignment schemes.

Since the answer may be large, output its remainder modulo $M$.

Input Format

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

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

If $m \neq 0$, then the next line contains $m$ pairs of integers, $p_1$, $q_1$, $p_2$, $q_2$, ..., $p_m$, $q_m$, where the $i$-th pair $p_i$, $q_i$ means that the label 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 an integer representing the number of schemes $\bmod M. Note that there is exactly one space between YESand the number. Otherwise, outputNO`.

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 $100\%$ of the testdata, it is guaranteed that

• $1 \leq T \leq 10$.
• $1 \leq n \leq 300$, $0 \leq m \leq n$, $2 \leq M \leq 10^9$.
• $1 \leq p_i, q_i \leq n$.
• All $p_i$ are distinct.

Translated by ChatGPT 5