C. Cable Network
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Chen works at Endfield Industries. She is building a communication network on a remote planet and needs to connect $$$n$$$ relay stations, numbered from $$$1$$$ to $$$n$$$, using exactly $$$n-1$$$ cables.

The stations are represented by distinct points in the plane. A cable is a straight line segment between two stations. It must not pass through other stations. Two cables must not intersect, except at a point where both cables end.

Every pair of stations must be connected by a path consisting of at most four cables.

Find a network of exactly $$$n - 1$$$ cables satisfying these conditions, or determine that no such network exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$, denoting the number of stations ($$$2 \le n \le 2 \cdot 10^5$$$).

The $$$i$$$-th of the following $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$, denoting the coordinates of station $$$i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$). All stations are at distinct locations.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print "$$$\texttt{NO}$$$" if no valid network exists.

Otherwise, print "$$$\texttt{YES}$$$", followed by $$$n-1$$$ pairs of integers $$$u$$$ and $$$v$$$, each describing a cable connecting stations $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$; $$$u \ne v$$$). If there are multiple answers, print any of them.

Example
Input
2
6
1 1
4 1
2 2
3 2
1 3
4 3
6
1 1
2 1
3 1
4 1
5 1
6 1
Output
YES
3 1
4 6
2 4
5 1
3 4
NO