Vika and Her Friends
Contest: Codeforces Round 885 (Div. 2)
Difficulty rating: 900
Tags: games, math

Vika and her friends went shopping in a mall, which can be represented as a rectangular grid of rooms with sides of length $$$n$$$ and $$$m$$$. Each room has coordinates $$$(a, b)$$$, where $$$1 \le a \le n, 1 \le b \le m$$$. Thus we call a hall with coordinates $$$(c, d)$$$ a neighbouring for it if $$$|a - c| + |b - d| = 1$$$.

Tired of empty fashion talks, Vika decided to sneak away unnoticed. But since she hasn't had a chance to visit one of the shops yet, she doesn't want to leave the mall. After a while, her friends noticed Vika's disappearance and started looking for her.

Currently, Vika is in a room with coordinates $$$(x, y)$$$, and her $$$k$$$ friends are in rooms with coordinates $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, ... $$$, (x_k, y_k)$$$, respectively. The coordinates can coincide. Note that all the girls must move to the neighbouring rooms.

Every minute, first Vika moves to one of the adjacent to the side rooms of her choice, and then each friend (seeing Vika's choice) also chooses one of the adjacent rooms to move to.

If at the end of the minute (that is, after all the girls have moved on to the neighbouring rooms) at least one friend is in the same room as Vika, she is caught and all the other friends are called.

Tell us, can Vika run away from her annoying friends forever, or will she have to continue listening to empty fashion talks after some time?

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n, m, k \le 100$$$) — the sizes of the mall and the number of Vika's friends.

The second line of each test case contains a pair of integers $$$x$$$ and $$$y$$$ ($$$1 \le x \le n$$$, $$$1 \le y \le m$$$) — the coordinates of the room where Vika is.

Each of the next $$$k$$$ lines of each test case contains a pair of integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$) — the coordinates of the room where the $$$i$$$-th friend is.

Output format:
For each test case, output "YES" if Vika can run away from her friends forever, otherwise output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the friend will never catch up with Vika, because Vika can always move to the room diagonally opposite to the one where the friend is.

In the second test case, no matter where Vika goes, each of her friends can catch her after the first move.

In the third test case, Vika and her friend will always be in different halls.

Example input:
6
2 2 1
1 1
1 2
2 2 2
1 1
2 2
2 2
1 2 1
1 1
1 2
5 5 4
3 3
1 1
1 5
5 1
5 5
2 2 2
1 1
2 1
1 2
3 4 1
1 2
3 3

Example output:
YES
NO
YES
NO
YES
YES

Editorial:
Let's color the halls of a rectangle in a chess coloring. Then Vika will be able to escape from her friends infinitely only if none of her friends is on a cell of the same color as Vika.
This observation seems intuitively clear, but let's formalize it.
$$$\Leftarrow)$$$ It is true, because if initially Vika and her friend were in halls of different colors, then after one move they will remain in halls of different colors.
$$$\Rightarrow)$$$ Let's choose any of the friends who is in a hall of the same color as Vika. We will show how the friend will act to catch Vika in a finite time. First, let's define a quantity that we will call the area to Vika:
• If Vika and the friend are in the same column, then the area to Vika is equal to the sum of the areas of all rows in the direction of Vika and the row where the friend is located.
• If Vika and the friend are in the same row, then the area to Vika is equal to the sum of the areas of all columns in the direction of Vika and the column where the friend is located.
• Otherwise, the area to Vika is equal to the area of the quadrant in which Vika is located relative to the friend.
• If Vika is in the same column as the friend. If Vika goes towards the friend, then the friend goes towards her, reducing the distance. If Vika goes in the opposite direction, then the friend also goes towards her, reducing the area to Vika. If Vika goes along the row, then the friend goes towards Vika along the column, which also reduces the area to Vika.
• If Vika is in the same row as the friend. If Vika goes towards the friend, then the friend goes towards her, reducing the distance. If Vika goes in the opposite direction, then the friend also goes towards her, reducing the area to Vika. If Vika goes along the column, then the friend goes towards Vika along the row, which also reduces the area to Vika.
• If Vika and the friend are in different rows and columns. If Vika goes towards the friend along the row, then the friend goes towards her along the column, reducing the distance. If Vika goes towards the friend along the column, then the friend goes towards her along the row, reducing the distance. If Vika goes away from the friend, then the friend makes a move in the same direction, thereby reducing the area to Vika.