Problema A - Corridas de Berlindes

Apesar de pouco falado, poucos desportos têm ganho mais espetadores do que as corridas de berlindes (em especial as Olimpíadas da Nutação Intensiva). Neste desporto há N berlindes que competem entre si para ver quem é o mais rápido. Como responsável por organizar as corridas das ONI, não podes perder esta oportunidade para mostrar aos novos fãs o melhor que o desporto tem para dar! Para tal, queres organizar as mais diversas e entusiasmantes corridas - os fãs não gostam que as corridas sejam iguais! Neste caso, a diversidade mede-se pelas características dos berlindes: o i-ésimo berlinde tem uma agilidade A_i e uma velocidade V_i, ambos números inteiros.

Parte I

Para manter a competição interessante queres evitar berlindes iguais, ou seja, com a mesma agilidade e a mesma velocidade. Isto garante que as corridas são o mais variadas possível. Como responsável pela organização, queres saber, dado os teus N berlindes, quantos berlindes diferentes tens?

Exemplo

Se N = 5 e os berlindes tiverem as seguintes agilidades e velocidades, respetivamente: (1, 2), (3, 4), (1, 2), (1, 4), (3, 2), então há 4 berlindes diferentes porque há dois berlindes com agilidade 1 e velocidade 2.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Parte II

A competição é feita por corridas a pares, ou seja, cada berlinde participa em exatamente uma corrida contra cada outro berlinde. Isto significa que há uma corrida entre os berlindes 1 e 2, uma corrida entre o 1 e o 3, etc, para todos os pares de berlindes possíveis. Em cada corrida, o berlinde vencedor é aquele que tem tanto a sua agilidade como a sua velocidade superiores às do outro berlinde. Se não houver um berlinde assim, a corrida resulta num empate.

Conseguiste reunir os berlindes mais interessantes e a competição está pronta para começar, mas tens uma curiosidade enorme e queres saber quem será o berlinde vencedor da competição. A questão é: no final da competição, depois de cada berlinde correr contra todos os outros berlindes, quantas vitórias vai ter o campeão do torneio?

Exemplo

Supões que N = 5 e os berlindes tiverem as seguintes agilidades e velocidades, respetivamente: (1, 2), (3, 4), (1, 2), (1, 4), (3, 2). O segundo berlinde (3, 4) ganha a corrida contra o primeiro berlinde (1, 2), visto que a sua agilidade (3) é maior que a do primeiro berlinde (1) e a sua velocidade (4) também (2). De facto, o campeão é o segundo berlinde com duas 2 vitórias, contra o primeiro e o terceiro berlinde, visto que todas as restantes corridas acabam com um empate.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 4 grupos com restrições adicionais diferentes:

Input

Nota: O formato de input é igual para todas as partes.

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com um inteiro N, representando o número de berlindes.

Seguem-se N linhas, cada uma contendo dois inteiros separados por espaços, sendo que a i-ésima linha contém os valores de agilidade A_i e velocidade V_i do i-ésimo berlinde.

Output

O output deve conter uma linha com um inteiro representando a resposta ao caso de teste:

• Parte I: o número de berlindes distintos;
• Parte II: o número de vitórias do vencedor;

Input do Exemplo 1

1
5
1 2
3 4
1 2
1 4
3 2

Output do Exemplo 1

4

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.

Input do Exemplo 2

2
5
1 2
3 4
1 2
1 4
3 2

Output do Exemplo 2

2

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.