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

Автобусні маршрути

Автобусні маршрути

В одній країні, яка має прямокутну форму, мережа міжміських магістралей має дуже простий вигляд -- кожна така магістраль являє собою відрізок прямої, що йде строго з півночі на південь або з заходу на схід, з'єднуючи протилежні сторони границі країни. На перетині дяких магістралей знаходяться самі міста, при цьому ніякі два міста не знаходяться на одній магістралі. Країна була достатньо багатою і тому не дуже розумно витрачала бюджетні кошти. Так, наприклад, між кожною парою міст існував прямий автобусний маршрут, який здійснював перевезення пасажирів з одного міста в інше одним з найкоротших шляхів без зупинок. Тим не менше, при плануванні бюджету на наступний рік раптом (як це завжди і буває) виявилось, що прибуток від міжміських перевезень у рази менший витрат на їх обслуговування. У зв'язку з цим було прийняте рішення максимально скоротити кількість маршрутів. При цьому, щоб народ не збунтувався із-за необхідності пересадок, вирішено було зробити це так, щоб відстань, яку потрібно проїхати між довільними двома містами, як і раніше залишалась мінімальною. \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} -- мінімальне число автобусних маршрутів, які потрібно залишити.
Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3
1 1
4 5
7 4
Вихідні дані #1
3