Moo Particle Interactions

In this problem, FJ's cows have discovered a new subatomic particle called the "Moo Particle". They are conducting an experiment with \( N \) Moo Particles (\(1 \le N \le 10^5\)). Each particle \( i \) has a spin represented by two integers \(x_i\) and \(y_i\) (\(-10^9 \le x_i, y_i \le 10^9\)).

An interaction may occur between two particles \(i\) and \(j\) if and only if \(x_i \le x_j\) and \(y_i \le y_j\). During an interaction, exactly one of the two particles may disappear (the other remains unaffected). At any given time, at most one interaction occurs.

The cows want to know the minimum possible number of Moo Particles remaining after performing an arbitrary sequence of interactions.

Hint: You can view this as a partial order in which particles can "cover" each other when both coordinates are less than or equal. By appropriately choosing the interactions (eliminating particles in chains), the answer is equal to the size of a maximum antichain in this poset. By Dilworth's theorem, this is equivalent to the minimum number of chains required to cover the set of particles.

Mathematical Formulation:
Given a set of particles \(\{(x_i, y_i)\}_{i=1}^N\), find the minimum number \(K\) such that the set can be partitioned into \(K\) chains, where a chain is a sequence \((x_{i_1}, y_{i_1}), (x_{i_2}, y_{i_2}), \dots, (x_{i_m}, y_{i_m})\) with \(x_{i_1} \le x_{i_2} \le \cdots \le x_{i_m}\) and \(y_{i_1} \le y_{i_2} \le \cdots \le y_{i_m}\).

inputFormat

The first line contains a single integer \(N\), the number of Moo Particles.

Each of the following \(N\) lines contains two space-separated integers \(x_i\) and \(y_i\) representing the spin coordinates of particle \(i\>.

outputFormat

Output a single integer, the minimum possible number of Moo Particles remaining after a sequence of interactions.

sample

1
0 0

1