Problem Background

Can we wait until the dream awakens?

Problem Description

Yue had a dream. In the dream, she received an integer sequence of length $n$, denoted as $a_1, \ldots, a_n$, where $n \ge 5$.

The dream has ended. Yue forgot some elements of the sequence, leaving blanks. Fortunately, she remembers $m$ non-blank positions. Yue wants to fill in the blanks to restore the entire sequence.

Yue also remembers that the sequence in the dream has a 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 wonders if it is possible to restore a sequence that satisfies this property (if not, she must have remembered it wrong). If possible, output Yes; otherwise, output No.

Input Format

This problem contains multiple test cases.

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

For each test case:

• The first line contains two integers $n$ and $m$, where $n \ge 5$ and $m$ represents the number of non-blank positions in $a_i$.
• The next $m$ lines, each containing two integers $p_i$ and $x_i$, indicate that $a_{p_i}$ is non-blank and equals $x_i$. It is guaranteed that $p_i$ are distinct.

Output Format

For each test case, output a string Yes or No, indicating whether the original sequence exists.

The case of the string does not matter in this problem, i.e., yes, yeS, yEs, Yes, YEs, YeS, yES, YES are all considered as Yes, and similarly for No.

Sample Input and Output

Input Sample #1

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

Output Sample #1

Yes
No
Yes

Input Sample #2

1
5 2
1 -2
5 -10

Output Sample #2

Yes

Input Sample #3

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

Output Sample #3

Yes
No

Notes

[Sample Explanation #1]

For the first test case, the current sequence is $[1, ?, ?, 4, 5]$. A possible original sequence is $[1, 2, 3, 4, 5]$, which satisfies the property.

For the second test case, the current sequence is $[1, 4, 7, 1, 5, 4]$. It can be proven that no sequence satisfying the property exists. This example reminds you that $p$ is not necessarily given in ascending order.

For the third test case, the current sequence is $[?, ?, ?, ?, ?]$. Possible original sequences include $[0, 0, 0, 0, 0]$ or $[-1, -1, -1, -1, -1]$. This example reminds you that $m$ can be zero, and the original sequence can contain negative numbers or zero.

[Data Range]

Let $\sum n$ denote the sum of $n$ in a single test point.

For all test data, $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 $p_i$ are distinct within the same data set.

This problem is bundled test.

• 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 additional constraints.

见题面 Input 部分

见题面 Output 部分