Bạn có \(N\) (\(2\le N\le 10^5\), \(N\) chẵn) điểm \((x_i,y_i)\) (\(1\le x_i,y_i\le 10^6\)) trên một mặt phẳng tọa độ hai chiều vô hạn.

Bạn có thể thực hiện hai loại thao tác sau đây bao nhiêu lần tùy ý:

• Chọn hai điểm kề trực tiếp với nhau (khoảng cách Manhattan bằng \(1\)) và xóa cả hai điểm.
• Chọn hai điểm bất kỳ và hoán đổi tọa độ \(y\) của chúng. Cụ thể, hai điểm \((a,b)\) và \((c,d)\) lần lượt trở thành \((a,d)\) và \((c,b)\).

Hãy xác định liệu có thể xóa hết tất cả các điểm trên mặt phẳng hay không. Lưu ý rằng hai điểm có thể nằm tại cùng một tọa độ; chúng vẫn phải được coi là hai điểm khác nhau. Bạn cũng không được trực tiếp xóa hai điểm nằm tại cùng một tọa độ, vì xét theo đúng định nghĩa, chúng không kề trực tiếp với nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 5000\)), là số lượng bộ test.

Dòng đầu tiên của mỗi bộ test chứa số nguyên \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i\) và \(y_i\).

Đảm bảo tổng \(N\) trên tất cả các bộ test không vượt quá \(5\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in YES hoặc NO trên một dòng mới.

Ví dụ

4
2
1 1
1 1
4
6 10
7 11
8 1
8 1
6
1 2
1 3
1 4
1 5
10 10
11 10
6
1 1
1 1
1 1
1 1
10 10
11 11

NO
YES
YES
NO

Phân nhóm

• Test 2: \(T\le 1000\), \(N\le 6\).
• Test 3–5: \(N\le 100\).
• Test 6–11: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Silver Division — bài gốc tiếng Anh “Point Elimination”. Tác giả: Alex Pylypenko và Chongtian Ma. https://usaco.org/index.php?page=viewproblem2&cpid=1592