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.
🌊
Le coordinate:
Puoi pensare al fiume come all’asse OX del sistema di coordinate.
Le due parti della città si trovano al di sopra e al di sotto dell’asse X. Di conseguenza, le coordinate rappresentano la coordinata
x del punto di inizio/fine del ponte.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