eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Автобусные маршруты

Автобусные маршруты

Лимит времени 3 секунды
Лимит использования памяти 64 MiB

В одной стране, имеющей прямоугольную форму, сеть междугородних магистралей имеет очень простой вид – каждая такая магистраль представляет собой отрезок прямой, идущий строго с севера на юг или с запада на восток, соединяя противоположные стороны границы страны. На пересечении некоторых магистралей находятся сами города, при этом никакие два города не находятся на одной магистрали.

Страна была достаточно богатой и потому не очень разумно тратила бюджетные средства. Так, например, между каждой парой городов существовал прямой автобусный маршрут, осуществляющий перевозки пассажиров из одного города в другой одним из кратчайших путей без остановок.

Тем не менее, при планировании бюджета на следующий год вдруг (как это всегда и бывает) оказалось, что прибыль от междугородних перевозок в разы меньше затрат на их обслуживание. В связи с этим было принято решение максимально сократить число маршрутов. При этом, чтобы народ не взбунтовался из-за необходимости пересадок, решено было сделать это так, чтобы расстояние, которое требуется проехать между любыми двумя городами, по-прежнему оставалось минимальным.

Входные данные

В первой строке одно натуральное число N – количество городов, 2N10000.

Далее N строк по два целых неотрицательных числа x_i, y_i – номера магистралей, на пересечении которых стоят города (x_i – номер магистрали, идущей с севера на юг, y_i – с запада на восток).

Магистрали в каждом направлении нумеруются последовательно от 0 до 1000000. Магистрали, идущие с севера на юг, нумеруются с запада на восток, а магистрали, идущие с запада на восток, – с севера на юг.

Выходные данные

В первой строке одно целое число P – минимальное число автобусных маршрутов, которое необходимо оставить.

Пример

Входные данные #1
3
1 1
4 5
7 4
Выходные данные #1
3