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.
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