Costruzione di ponti
C’è una città attraversata da un bellissimo fiume proprio al centro. Il comune ha deciso di costruire ponti per collegare la città. Al momento, gli abitanti usano barche per attraversare il fiume, una soluzione poco pratica.
La città ha individuato n coppie di coordinate che potrebbero essere collegate da un ponte. Tuttavia, esiste una condizione: i ponti non possono incrociarsi (cioè un ponte non può sovrapporsi a un altro). È permesso invece condividere i punti di inizio o fine.
Dato l’elenco delle coppie di coordinate collegabili, si richiede di trovare il numero massimo di ponti che è possibile costruire senza violare tale requisito.
Input
La prima riga dell’input contiene un singolo intero n (1 ≤ n ≤ 100 000).
Le successive n righe contengono coppie di interi che rappresentano le coordinate collegabili (1 ≤ ≤ ).
Output
Il programma deve stampare un unico intero: il numero massimo di ponti che il comune può costruire.
Examples
Input | Output |
|---|---|
4 2 6 5 4 8 1 10 2 | 2 |
6 1 3 2 4 3 5 4 6 5 1 6 2 | 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB