Background

Original link: https://oier.team/problems/X2A.

Can we wait until the moment the dream wakes up.

Problem Description

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.

Input Format

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.

Output Format

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.

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

Yes
No
Yes

1
5 2
1 -2
5 -10

Yes

2
9 6
1 -856675560
8 479857596
5 -92942328
4 -283875636
3 -474808944
9 670790904
10 7
4 -32297373
10 -633066970
9 831032854
5 -43726758
2 -699796467
1 -918486370
8 612342951

Yes
No

Hint

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