P10852 [MX-X2-T1] "Cfz Round 4" Awaken

Original link: . --- Can we wait until the moment the dream wakes up. 

Yue had a dream. In the dream, she got an **integer** sequence $a_1, \ldots, a_n$ of length $n$, **where $\bm{n \ge 5}$**. Then she woke up. Yue forgot some elements of the sequence, leaving blanks. Luckily, Yue still remembers $m$ non-blank positions. Yue wants to fill in the blanks and restore the whole sequence. Yue also remembers that the sequence in the dream had the following property: for all distinct indices $x_1, x_2, x_3, x_4$ satisfying $x_2 + x_3 = x_1 + x_4$, it always holds that $a_{x_2} + a_{x_3} = a_{x_1} + a_{x_4}$. Yue wants to know whether it is possible to restore a sequence that satisfies the property (if not, then she remembered it wrong). If possible, output `Yes`; otherwise output `No`.

**This problem has multiple test cases.** The first line contains an integer $T$, the number of test cases. Then each test case is given as follows: - The first line contains two integers $n, m$, where $n \ge 5$, and $m$ is the number of positions in $a_i$ that are not blank. - The next $m$ lines each contain two integers $p_i, x_i$, meaning that $a_{p_i}$ is not blank and $a_{p_i} = x_i$. It is guaranteed that all $p_i$ are pairwise distinct.

For each test case, output a string `Yes` or `No`, indicating whether the original sequence exists. In this problem, the output is case-insensitive. That is, `yes`, `yeS`, `yEs`, `Yes`, `YEs`, `YeS`, `yES`, `YES` are all considered `Yes`, and similarly for `No`.

**Sample Explanation #1** For the $1$st test case, the current sequence is $[1, ?, ?, 4, 5]$. One possible original sequence is $[1, 2, 3, 4, 5]$. You can check that this sequence satisfies the property. For the $2$nd test case, the current sequence is $[1, 4, 7, 1, 5, 4]$. It can be proven that no original sequence satisfying the property exists. This sample reminds you that **$\bm p$ is not necessarily given in increasing order**. For the $3$rd test case, the current sequence is $[?, ?, ?, ?, ?]$. One possible original sequence is $[0, 0, 0, 0, 0]$, and of course $[-1, -1, -1, -1, -1]$ also works. This sample reminds you that $m$ can be $0$, and the original sequence may contain negative numbers or $0$. **Constraints** Let $\sum n$ denote the sum of $n$ within a single test file. For all testdata, $1 \le T \le 4 \times 10^4$, $5 \le n \le 2 \times 10^5$, $\sum n \le 2 \times 10^5$, $0 \le m \le n$, $1 \le p_i \le n$, $-10^{9} \le x_i \le 10^{9}$. It is guaranteed that within the same test case, all $p_i$ are pairwise distinct. **This problem uses bundled evaluation.** - Subtask 1 (20 points): $n \le 2000$ and $m = n$. - Subtask 2 (30 points): $n \le 6$, $|x| \le 7$. - Subtask 3 (20 points): $m = 2$. - Subtask 4 (30 points): no special constraints. Translated by ChatGPT 5