Construção de Pontes
Existe uma cidade atravessada por um belo rio bem no centro. A autarquia da cidade decidiu construir pontes para facilitar a ligação entre as duas margens. Atualmente, as pessoas usam barcos para fazer a travessia, o que não é muito prático.
A cidade identificou
n pares de coordenadas que podem ser ligados por uma ponte. Porém, existe uma condição: as pontes não podem cruzar-se (uma ponte não pode passar por cima da outra). No entanto, podem partilhar os seus pontos de início ou fim.Dadas as possíveis ligações entre os pares de coordenadas, pretende-se determinar o número máximo de pontes que a autarquia pode construir sem violar estas regras.
🌊
As coordenadas:
Pode imaginar o rio como o eixo OX do sistema de coordenadas.
As duas partes da cidade são as que ficam acima e abaixo do eixo X. Logo, as coordenadas representam a componente
x do ponto de partida/chegada da ponte.Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 100 000).As próximas
n linhas contêm pares de inteiros que representam as coordenadas a serem ligadas (1 ≤ ≤ ).Saída
O programa deve imprimir um único número inteiro — o número máximo de pontes que a autarquia pode construir.
Exemplos
Entrada | Saída |
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