В одной стране, имеющей прямоугольную форму, сеть междугородних магистралей имеет очень простой вид – каждая такая магистраль представляет собой отрезок прямой, идущий строго с севера на юг или с запада на восток, соединяя противоположные стороны границы страны. На пересечении некоторых магистралей находятся сами города, при этом никакие два города не находятся на одной магистрали.
Страна была достаточно богатой и потому не очень разумно тратила бюджетные средства. Так, например, между каждой парой городов существовал прямой автобусный маршрут, осуществляющий перевозки пассажиров из одного города в другой одним из кратчайших путей без остановок.
Тем не менее, при планировании бюджета на следующий год вдруг (как это всегда и бывает) оказалось, что прибыль от междугородних перевозок в разы меньше затрат на их обслуживание. В связи с этим было принято решение максимально сократить число маршрутов. При этом, чтобы народ не взбунтовался из-за необходимости пересадок, решено было сделать это так, чтобы расстояние, которое требуется проехать между любыми двумя городами, по-прежнему оставалось минимальным.
В первой строке одно натуральное число N – количество городов, 2 ≤ N ≤ 10000.
Далее N строк по два целых неотрицательных числа x_i, y_i – номера магистралей, на пересечении которых стоят города (x_i – номер магистрали, идущей с севера на юг, y_i – с запада на восток).
Магистрали в каждом направлении нумеруются последовательно от 0 до 1000000. Магистрали, идущие с севера на юг, нумеруются с запада на восток, а магистрали, идущие с запада на восток, – с севера на юг.
В первой строке одно целое число P – минимальное число автобусных маршрутов, которое необходимо оставить.