성

어느 사막 한가운데의 폐허를 찍은 위성 사진이 도착했다. 알고 보니 이 폐허는 약 2000년 전에 사라진 왕국의 고대 성이며, 사진으로 미루어 성의 평면도는 직교 다각형(rectilinear polygon) 모양임을 알 수 있다.

직교 다각형이란 모든 변이 수평 또는 수직인 다각형이다. 다시 말해, 그림 1처럼 각 꼭짓점에서 이웃한 두 변이 이루는 내각이 항상 $90^\circ$ 또는 $270^\circ$이다. 직교 다각형이 단순(simple)하다는 것은 (1) 모든 꼭짓점이 정확히 두 변과 맞닿아 있고, (2) 어떤 두 변도 공유하는 끝점 말고는 서로 만나지 않는 것을 뜻한다.

그림 1. (a) 단순한 직교 다각형. (b), (c) 단순하지 않은 직교 다각형: (b) 한 꼭짓점에 네 개의 변이 맞닿아 있거나, (c) 두 변이 서로 교차한다.

성은 세월을 이기지 못하고 기둥, 즉 단순 직교 다각형의 꼭짓점만 남았다. 성의 원래 모습을 되살리려면 이 기둥들이 어떻게 연결되어 있었는지 알아내야 한다. 그림 2가 그 예이다.

형식적으로, 정수 좌표를 가진 서로 다른 점 $n$개가 주어진다. 이 점들을 모두 수평 선분과 수직 선분으로, 경계를 따라 번갈아 이어서 단순 직교 다각형을 만들 수 있는지 판정하라. $n$개의 점 전부를 꼭짓점으로 하는 단순 직교 다각형을 복원할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

그림 2. (a) 입력으로 주어진 점들. (b) 그 점들로 복원한 단순 직교 다각형.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 점의 개수 $n$이 주어지며, $4 \le n \le 10{,}000$이다. 이어지는 $n$개의 줄에는 각 점의 $x$좌표와 $y$좌표를 나타내는 두 정수가 주어지며, 두 값 모두 $-10^6$ 이상 $10^6$ 이하이다. 한 테스트 케이스 안의 모든 점은 서로 다르다.

결과는 표준 출력으로 출력한다. 각 테스트 케이스마다 정확히 한 줄을 출력한다. 점들이 단순 직교 다각형을 이루면 YES를, 그렇지 않으면 NO를 출력한다.