Муу частинки#10309

Муу частинки

1 секунда

128 мегабайтів

Дуже легка

Під час карантину через спалах COWVID-19, корови фермера Джона знайшли новий спосіб розважитися: вони почали вивчати фізику на вищому рівні! Вони навіть відкрили нову субатомну частинку, яку назвали "муу частинкою".

Корови проводять експеримент з $n$ муу частинками. Кожна частинка $i$ має "спін", який описується двома цілими числами $x_{i}$ x_i і $y_{i}$ y_i, що знаходяться в діапазоні від $- 1 0^{9}$ -10^9 до $1 0^{9}$ 10^9 включно. Іноді дві муу частинки можуть взаємодіяти. Це можливо для частинок зі спінами $(x_{i}, y_{i})$ (x_i, y_i) і $(x_{j}, y_{j})$ (x_j, y_j), якщо виконується умова $x_{i} \leq x_{j}$ x_i \le x_j і $y_{i} \leq y_{j}$ y_i \le y_j. У такому випадку одна з цих двох частинок може зникнути (інша залишиться без змін). У будь-який момент часу може відбутися не більше однієї взаємодії.

Корови хочуть дізнатися мінімальну кількість муу частинок, які можуть залишитися після будь-якої можливої послідовності взаємодій.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5) - початкову кількість муу частинок. Кожен з наступних $n$ рядків містить два цілі числа, що представляють спін однієї частинки. У кожної частинки свій унікальний спін.

Вихідні дані

Виведіть одне ціле число - мінімальну кількість муу частинок, які можуть залишитися після будь-якої можливої послідовності взаємодій.

Приклади

Приклад 1

Приклад 2

Примітка

Приклад 1. Одна з можливих послідовностей взаємодії:

Частинки $1$ і $4$ взаємодіють, частинка $1$ зникає.
Частинки $2$ і $4$ взаємодіють, частинка $4$ зникає.
Частинки $2$ і $3$ взаємодіють, частинка $3$ зникає.

Залишається тільки частинка $2$ .

Приклад 2. Частинка $3$ не може взаємодіяти з жодною з інших двох частинок, тому вона повинна залишитися. Також повинна залишитися хоча б одна з частинок $1$ або $2$ .