eolymp
bolt
Try our new interface for solving problems
Problems

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

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

В одной стране, имеющей прямоугольную форму, сеть междугородних магистралей имеет очень простой вид -- каждая такая магистраль представляет собой отрезок прямой, идущий строго с севера на юг или с запада на восток, соединяя противоположные стороны границы страны. На пересечении некоторых магистралей находятся сами города, при этом никакие два города не находятся на одной магистрали. Страна была достаточно богатой и потому не очень разумно тратила бюджетные средства. Так, например, между каждой парой городов существовал прямой автобусный маршрут, осуществляющий перевозки пассажиров из одного города в другой одним из кратчайших путей без остановок. Тем не менее, при планировании бюджета на следующий год вдруг (как это всегда и бывает) оказалось, что прибыль от междугородних перевозок в разы меньше затрат на их обслуживание. В связи с этим было принято решение максимально сократить число маршрутов. При этом, чтобы народ не взбунтовался из-за необходимости пересадок, решено было сделать это так, чтобы расстояние, которое требуется проехать между любыми двумя городами, по-прежнему оставалось минимальным. \InputFile В первой строке одно натуральное число \textbf{N} -- количество городов, \textbf{2} ≤ \textbf{N} ≤ \textbf{10000}. Далее \textbf{N} строк по два целых неотрицательных числа \textbf{x_i}, \textbf{y_i} -- номера магистралей, на пересечении которых стоят города (\textbf{x_i} -- номер магистрали, идущей с севера на юг, \textbf{y_i} -- с запада на восток). Магистрали в каждом направлении нумеруются последовательно от \textbf{0} до \textbf{1000000}. Магистрали, идущие с севера на юг, нумеруются с запада на восток, а магистрали, идущие с запада на восток, -- с севера на юг. \OutputFile В первой строке одно целое число \textbf{P} -- минимальное число автобусных маршрутов, которое необходимо оставить.
Time limit 3 seconds
Memory limit 64 MiB
Input example #1
3
1 1
4 5
7 4
Output example #1
3