Вам даны $$$n$$$ ладей на бесконечной шахматной доске.
$$$i$$$-я из них находится в клетке $$$(r_i, c_i)$$$.
За один ход вы можете переместить любую ладью на любую клетку в той же строке/столбце. Иначе говоря, за один ход вы можете выбрать любое $$$i$$$ а затем либо заменить $$$r_i$$$ на любое целое число, либо заменить $$$c_i$$$ на любое целое число. Вы не можете двигать ладью в клетку, которая содержит другую ладью.
Четыре разные ладьи $$$a, b, c, d$$$ образуют симпатичную фигуру если вы можете найти прямоугольник, что $$$a,b,c,d$$$ это его углы. Иначе говоря, если множество клеток $$$\{(r_a, c_a), (r_b, c_b), (r_c, c_c), (r_d, c_d)\}$$$ совпадает с множеством $$$\{(x_1, y_1), (x_1, y_2), (x_2, y_1), (x_2, y_2)\}$$$ для какого-то набора целых чисел $$$x_1, x_2, y_1, y_2$$$, где $$$x_1 \neq x_2$$$ и $$$y_1 \neq y_2$$$
Например, белые ладьи на следующей картинке образуют симптатичную фигуру.
Ваша задача — найти минимальное количество действий, которое нужно совершить, чтобы получить симпатичную фигурку.
Иначе говоря, вам нужно найти минимальное число операций, после которого может найтись прямоугольник, который содержит ладьи в четырех углах.
В первой строке записано одно целое число $$$t$$$ ($$$1 \leq t \leq 25\,000$$$): количество наборов входных данных.
Далее следуют описания $$$t$$$ наборов входных данных.
В первой строке записано одно целое число $$$n$$$ ($$$4 \leq n \leq 100\,000$$$).
В $$$i$$$-й из следующих $$$n$$$ строк записаны два целых числа $$$r_i, c_i$$$ ($$$1 \leq r_i, c_i \leq 10^9$$$)
Для каждой пары $$$i, j$$$, что $$$i \neq j$$$, выполнено $$$r_i \neq r_j$$$ или $$$c_i \neq c_j$$$.
Сумма по всем $$$n$$$ не превосходит $$$100\,000$$$.
Для каждого набора входных данных, выведите одно целое число: минимальное количество действий, которое нужно совершить, чтобы получить хотя бы одну симпатичную фигуру среди данных ладей.
| {Баллы} | {Ограничения} | |
| 1 | 10 | $$$n \leq 4$$$ |
| 2 | 10 | $$$n \leq 50$$$ |
| 3 | 10 | $$$n \le 200$$$ |
| 4 | 30 | $$$n \le 2000$$$ |
| 5 | 40 | $$$n \le 10^5$$$ |
5 4 4 4 1 1 2 2 3 3 4 4 4 4 1 1 4 2 2 6 3 2 2 1 1 2 3 3 3 4 3 1 5 1 1 1 2 1 3 1 4 5 5 4 1000000000 1000000000 1000000000 1 2 2 1000000000 999999999
4 2 1 3 3
Одно из возможных оптимальных решений для первого набора входных данных из примера:
Одно из возможных оптимальных решений для второго набора входных данных из примера:
