CF2215E Star Map

Funni-chan loves watching stars. There are $ n $ stars in the sky, which can be regarded as points on a plane with Cartesian coordinates. The coordinates of the $ i $ -th star are $ (x_i, y_i) $ . It is guaranteed that all $ x_1, x_2, \ldots, x_n $ are pairwise distinct, and all $ y_1, y_2, \ldots, y_n $ are pairwise distinct. The stars are numbered from $ 1 $ to $ n $ in the order they are given in the input. Funni-chan wants to connect some pairs of these stars to form a constellation. She defines the basic unit of a constellation as a triangle formed by three stars connected pairwise. A triangle is called harmonious if there exists an axis-aligned rectangle such that all three vertices of the triangle lie on the boundary of the rectangle. Funni-chan imposes the following constraints on the constellation: - Every triangle in the constellation must be harmonious. - The interiors of any two triangles in the constellation must be disjoint. Note that the boundary of a triangle is not considered part of its interior. Under these constraints, Funni-chan wants her constellation to contain the maximum possible number of triangles. Your task is to find this maximum number and construct a valid constellation that achieves it.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2\cdot 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the number of stars. Each of the next $ n $ lines contains two integers $ x_i $ and $ y_i $ ( $ -10^9\le x_i, y_i \le 10^9 $ ) — the coordinates of the $ i $ -th star. It is guaranteed that all $ x_i $ -s are pairwise distinct, and all $ y_i $ -s are pairwise distinct. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

In the first line of each test case, you should print a single integer $ m $ ( $ 0\le m\le 2\cdot n $ ) — the maximum possible number of triangles in the constellation. Then $ m $ lines follow, each line containing three distinct positive integers $ a_i $ , $ b_i $ , and $ c_i $ ( $ 1 \le a_i, b_i, c_i \le n $ ), denoting the indices of the three stars forming the $ i $ -th triangle.

The first test case of the example is illustrated below： The second test case of the example is illustrated below: