Polycarp got the accompanying issue: given a framework piece of size 2×n, a few cells of it are obstructed. You want to check in case it is feasible to tile all free cells utilizing the 2×1 and 1×2 tiles (dominoes). For instance, if
Correct answer will be upvoted else Multiple Downvoted. Computer science.
Polycarp got the accompanying issue: given a framework piece of size 2×n, a few cells of it are obstructed. You want to check in case it is feasible to tile all free cells utilizing the 2×1 and 1×2 tiles (dominoes).
For instance, if n=5 and the strip appears as though this (dark cells are obstructed)
Polycarp handily tackled this errand and accepted his New Year's gift. Would you be able to settle it?
Input
The main line contains an integer t (1≤t≤104) — the number of experiments. Then, at that point, t experiments follow.
Each experiment is gone before by a vacant line.
The main line of each experiment contains two integers n and m (1≤n≤109, 1≤m≤2⋅105) — the length of the strip and the number of impeded cells on it.
Every one of the following m lines contains two integers ri,ci (1≤ri≤2,1≤ci≤n) — numbers of lines and sections of hindered cells. It is ensured that all impeded cells are unique, for example (ri,ci)≠(rj,cj),i≠j.
It is ensured that the amount of m over all experiments doesn't surpass 2⋅105.
Output
For each experiment, print on a different line:
"Indeed", in case it is feasible to tile all unblocked squares with the 2×1 and 1×2 tiles;
"NO" in any case.
You can output "YES" and "NO" regardless (for instance, the strings yEs, indeed, Yes and YES will be perceived as certain).
Step by step
Solved in 4 steps with 1 images
