Construcción de Puentes
Hay una ciudad con un hermoso río que la atraviesa justo por el centro. La municipalidad ha decidido construir puentes para conectar la ciudad. En este momento, la gente utiliza botes para cruzar el río, lo cual no resulta muy conveniente.
La ciudad ha identificado
n pares de coordenadas que podrían unirse mediante un puente. Sin embargo, existe un requisito: los puentes no pueden cruzarse entre sí (es decir, un puente no puede pasar por encima de otro). No obstante, sí está permitido que compartan puntos de inicio o final.Dadas las parejas de coordenadas que se pueden conectar, se te pide determinar el número máximo de puentes que la municipalidad puede construir sin incumplir los requisitos.
🌊
Las coordenadas:
Puedes imaginar el río como el eje OX de un sistema de coordenadas.
Las dos partes de la ciudad son las que se encuentran por encima y por debajo de este eje. Por lo tanto, las coordenadas representan la posición
x del inicio o fin del puente.Entrada
La primera línea de la entrada contiene un único número entero
n (1 ≤ n ≤ 100 000).Las siguientes
n líneas contienen pares de enteros que representan las coordenadas que podrían conectarse (1 ≤ ≤ ).Salida
El programa debe imprimir un único número entero, que es la cantidad máxima de puentes que la municipalidad podría construir.
Ejemplos
Entrada | Salida |
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