O laboratório do Professor JOI pesquisa $N$ tipos de minerais. Existem 2 lâminas de cada tipo de mineral. Ao todo, existem $2N$ lâminas, numeradas de $1$ a $2N$.

Um dia, o assistente Bitaro deixou cair a caixa que continha as $2N$ lâminas e ficou sem saber quais lâminas eram do mesmo tipo de mineral.

O laboratório possui um aparelho que consegue contar o número de tipos de minerais presentes nas lâminas inseridas nele, medindo o comprimento de onda que cada mineral absorve. Bitaro pretende identificar os $N$ pares do mesmo tipo de mineral entre as $2N$ lâminas. Inicialmente, nenhuma lâmina está inserida no aparelho. Bitaro pode realizar as seguintes operações:

• Inserir uma lâmina no aparelho e descobrir quantos tipos de minerais estão no aparelho.
• Retirar uma lâmina do aparelho e descobrir quantos tipos de minerais estão no aparelho.

Para que o Professor JOI não perceba que Bitaro causou problemas, Bitaro pode realizar essas operações no máximo $1\,000\,000$ de vezes no total.

Escreva um programa que, dado o número de tipos de minerais, utilize o aparelho para determinar todos os pares do mesmo tipo de mineral.

Detalhes de implementação

Você deve enviar um arquivo.

O arquivo deve se chamar minerals.cpp. Ele deve implementar a função a seguir. O programa deve incluir minerals.h.

• void Solve(int N)

  Esta função é chamada exatamente uma vez para cada caso de teste.

  • O parâmetro N representa $N$, o número de tipos de minerais.

  Seu programa pode chamar as funções a seguir.

  • int Query(int x)

    Para o índice da lâmina que você especificar, esta função retira a lâmina do aparelho se ela já estiver nele, ou a insere no aparelho caso contrário. Em seguida, retorna o número de tipos de minerais no aparelho.

    • Você especifica o índice $x$ da lâmina por meio do parâmetro x. Ele deve satisfazer $1 \le x \le 2N$. Caso contrário, seu programa recebe o veredito Wrong Answer [1].
    • A função Query não deve ser chamada mais de $1\,000\,000$ de vezes. Caso contrário, seu programa recebe o veredito Wrong Answer [2].

  • void Answer(int a, int b)

    Use esta função para informar os pares do mesmo mineral.

    • Os parâmetros a e b indicam que a lâmina de número $a$ e a lâmina de número $b$ são do mesmo tipo de mineral. Eles devem satisfazer $1 \le a \le 2N$ e $1 \le b \le 2N$. Caso contrário, seu programa recebe o veredito Wrong Answer [3]. Se um mesmo valor aparecer mais de uma vez no conjunto de todas as ocorrências de a e b, seu programa recebe o veredito Wrong Answer [4]. Se forem especificadas lâminas de tipos de minerais diferentes, seu programa recebe o veredito Wrong Answer [5].

  A função Answer deve ser chamada exatamente $N$ vezes. Se o número de chamadas à função Answer não for $N$ ao terminar a execução da função Solve, seu programa recebe o veredito Wrong Answer [6].

Observações importantes

• Seu programa pode implementar outras funções para uso interno ou usar variáveis globais.
• Seu programa não deve usar a entrada padrão nem a saída padrão. Seu programa não deve se comunicar com outros arquivos por nenhum meio. Entretanto, pode escrever informações de depuração na saída de erro padrão.

Compilação e execução de teste

Você pode baixar da página do concurso um arquivo compactado que contém o avaliador de exemplo para testar seu programa. O arquivo compactado também contém um arquivo-fonte de exemplo para seu programa.

O avaliador de exemplo é o arquivo grader.cpp. Para testar seu programa, coloque grader.cpp, minerals.cpp e minerals.h no mesmo diretório e execute o comando a seguir para compilar seus programas.

g++ -std=gnu++14 -O2 -o grader grader.cpp minerals.cpp

Quando a compilação for bem-sucedida, o arquivo executável grader será gerado.

Observe que o avaliador real é diferente do avaliador de exemplo. O avaliador de exemplo será executado como um único processo, que lê os dados da entrada padrão e escreve os resultados na saída padrão.

Entrada do avaliador de exemplo

O avaliador de exemplo lê os seguintes dados da entrada padrão.

$$ \begin{array}{ll} N \\ X_1 & Y_1 \\ \vdots \\ X_N & Y_N \end{array} $$

$X_i$ e $Y_i$ ($1 \le i \le N$) indicam que a lâmina de número $X_i$ e a lâmina de número $Y_i$ são do mesmo tipo de mineral.

Saída do avaliador de exemplo

Quando o programa termina com sucesso, o avaliador de exemplo escreve as seguintes informações na saída padrão (as aspas servem para maior clareza).

• Se seu programa for considerado correto, ele escreve o número de chamadas à função Query na forma Accepted: 100.
• Se seu programa receber o veredito de resposta incorreta, ele escreve o tipo na forma Wrong Answer [1].

Se seu programa receber vários tipos de veredito de resposta incorreta, o avaliador de exemplo informa apenas um deles.

Restrições

Consulte a seção “Entrada do avaliador de exemplo” para a definição de $X_i$ e $Y_i$.

• $1 \le N \le 43\,000$.
• $1 \le X_i \le 2N$ ($1 \le i \le N$).
• $1 \le Y_i \le 2N$ ($1 \le i \le N$).
• $X_i \ne X_j$ ($1 \le i < j \le N$).
• $Y_i \ne Y_j$ ($1 \le i < j \le N$).
• $X_i \ne Y_j$ ($1 \le i \le N$, $1 \le j \le N$).

Subtarefas

1. (6 pontos) $N \le 100$.
2. (25 pontos) $N \le 15\,000$, $1 \le X_i \le N$, $N+1 \le Y_i \le 2N$ ($1 \le i \le N$).
3. (9 pontos) $N \le 15\,000$.
4. (30 pontos) $N \le 38\,000$.
5. (5 pontos) $N \le 39\,000$.
6. (5 pontos) $N \le 40\,000$.
7. (5 pontos) $N \le 41\,000$.
8. (5 pontos) $N \le 42\,000$.
9. (10 pontos) Nenhuma restrição adicional.

Exemplo de comunicação

A seguir estão uma entrada de exemplo para o avaliador de exemplo e as chamadas de funções correspondentes.

Entrada 1

4
1 5
2 6
3 4
7 8

Chamadas de exemplo