33962번 - 통나무 스페셜 저지

문제

포스텍 캠퍼스 바깥쪽에는 PPC라는 이름의 거대한 통나무가 서있으며, 포스텍의 일부 학생들이 이 통나무를 붙들고 있었다. 하지만 포스텍의 모든 학생은 졸업을 하기 마련. 이 학생들 또한 졸업을 하게 되면서 통나무를 들 사람이 없어졌고, 그대로 통나무가 학교 쪽으로 쓰러져버리는 대참사가 발생했다! 다행히도 인명피해는 일어나지 않았지만, 건물 사이를 잇는 전선이 모두 끊어져버려 학교에 매우 큰 피해가 발생했다. 피해가 더 늘어나는 것을 막기 위해 여러분은 건물들 사이의 전선을 복구해야 한다.

학교는 2차원 평면으로 나타낼 수 있으며, 이 위에 총 $N$개의 건물이 있다. $i$번째 건물의 좌표는 $(X_i, Y_i)$이다. 쓰러진 통나무는 2차원 평면 위 선분으로 나타낼 수 있으며, 통나무의 양 끝점은 $T_1 = (Tx_1, Ty_1),ドル $T_2 = (Tx_2, Ty_2)$이다. 어떤 건물도 통나무 위에 위치하지 않으며, 각 건물의 위치는 모두 다르다.

여러분은 아래의 조건을 만족하며 전선을 복구해야 한다.

• 두 건물을 전선으로 잇는다는 것은, 2차원 평면 위에서 건물에 해당하는 두 점을 선분으로 잇는 것으로 나타낼 수 있다.
• 정확히 $N-1$개의 전선만을 사용하여 모든 건물이 서로 연결되도록 해야 한다. 즉, 연결된 건물이 트리 구조를 이루어야 한다.
• 어떤 두 전선도 서로 교차하면 안되며, 전선과 통나무도 서로 교차하면 안된다. 한 선분의 끝 점이 다른 선분 위에 있는 것도 교차하는 것이며, 두 선분이 끝 점에서 만나는 것은 교차하는 것이 아니다.

입력

첫 번째 줄에 건물의 개수 $N$이 주어진다. $(2 \le N \le 10^5)$

다음 $N$개의 줄 중 $i$번째 줄에는 정수 $X_i, Y_i$가 공백으로 구분되어 주어지며, 이는 $i$번째 건물의 위치가 $(X_i, Y_i)$임을 의미한다. ($-10^9 \le X_i , Y_i \le 10^9$)

$N + 2$번째 줄에는 통나무의 위치를 나타내는 4ドル$개의 정수 $Tx_1, Ty_1, Tx_2, Ty_2$가 공백으로 구분되어 주어진다. 이는 통나무의 한쪽 끝 좌표가 $(Tx_1, Ty_1)$이며, 다른 쪽 끝 좌표가 $(Tx_2, Ty_2)$임을 의미한다. ($-10^9 \le Tx_1, Ty_1, Tx_2, Ty_2 \le 10^9$)

출력

만약 조건을 만족하며 전선들을 복구할 수 있다면 첫 번째 줄에 YES를 출력한다.

두 번째 줄부터 $N$번째 줄까지 $a_i, b_i$를 출력한다. 이는 건물 $a_i$와 $b_i$를 전선으로 잇는 것을 의미한다. 모든 전선들은 문제의 조건을 만족해야 한다.

전선들을 복구할 수 없다면 NO를 출력한다.

제한

힌트

실제로 쓰러질 일이 없길 기원합니다.