Lát domino trên bảng 2 hàng

Cho một bảng hình chữ nhật kích thước $2\times n$ (2 hàng, $n$ cột). Một số ô của bảng bị chặn, các ô còn lại là ô trống.

Hãy kiểm tra xem có thể lát kín toàn bộ các ô trống bằng những quân domino kích thước $2\times 1$ và $1\times 2$ hay không. Mỗi quân domino phủ đúng hai ô trống kề cạnh nhau, hai quân domino không được chồng lên nhau, và không quân domino nào được phủ lên ô bị chặn.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm:
  • Dòng đầu chứa hai số nguyên $n$ và $m$ là số cột của bảng và số ô bị chặn.
  • $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $r_i$ và $c_i$ là chỉ số hàng và chỉ số cột của một ô bị chặn. Các ô bị chặn đôi một khác nhau và không nhất thiết được liệt kê theo thứ tự nào.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng riêng:

• YES nếu có thể lát kín mọi ô trống bằng domino;
• NO nếu không thể.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le {10}^9$
• $1\le m\le 2·{10}^5$
• $1\le r_i\le 2$, $1\le c_i\le n$
• Tổng $m$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ