Existem $N$ ilhas onde vivem castores, numeradas de $0$ a $N-1$. Estas ilhas estão ligadas por $N-1$ pontes bidirecionais. É possível viajar entre quaisquer ilhas utilizando algumas pontes. Cada ilha tem, no máximo, 18 pontes diretamente ligadas a ela. Em cada ilha vive um castor.

Por vezes, alguns castores reúnem-se numa ilha para realizar uma reunião. Quando se encontram exatamente três castores, reúnem-se na seguinte ilha:

A ilha que minimiza o número total de pontes que os três castores atravessam para se reunirem (essa ilha existe e é única).

Note que esta ilha pode coincidir com uma ilha onde vive um dos três castores.

Está interessado em saber como as $N$ ilhas estão ligadas por pontes. Não pode ir verificar as ilhas diretamente, por isso vai dar algumas instruções aos castores. Uma instrução consiste no seguinte:

• Especifica três ilhas $u$, $v$ e $w$ ($0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$, $v \ne w$) e faz com que os castores que vivem nas ilhas $u$, $v$ e $w$ realizem uma reunião.
• Depois, pode observar a ilha onde os três castores se reúnem.

Quer determinar como as ilhas estão ligadas utilizando poucas instruções.

Escreva um programa que, dado o número de ilhas, comunique com os castores e determine como as ilhas estão ligadas.

Detalhes de implementação

Deve submeter um ficheiro.

O nome do ficheiro é meetings.cpp. Este deve implementar a função seguinte. O programa deve incluir meetings.h.

• void Solve(int N)

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

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

O seu programa pode chamar as seguintes funções.

• int Query(int u, int v, int w)

Esta função devolve, para os índices das três ilhas que especificar, o índice da ilha onde os castores que nelas vivem se reúnem.

• Especifica os índices $u$, $v$ e $w$ das três ilhas através dos parâmetros u, v e w, respetivamente. Estes devem satisfazer $0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$ e $v \ne w$. Caso contrário, o seu programa é considerado como Resposta errada [1].

• A função Query não deve ser chamada mais de $100\,000$ vezes. Caso contrário, o seu programa é considerado como Resposta errada [2].

• void Bridge(int u, int v)

Utilizando esta função, indica como as ilhas estão ligadas por pontes.

• Os parâmetros u e v indicam que as ilhas $u$ e $v$ estão diretamente ligadas por uma ponte.
• Se $0 \le u < v \le N-1$ não se verificar, o seu programa é considerado como Resposta errada [3].
• Se as ilhas $u$ e $v$ não estiverem diretamente ligadas por uma ponte, o seu programa é considerado como Resposta errada [4].
• Se a função Bridge for chamada várias vezes com os mesmos parâmetros u e v, o seu programa é considerado como Resposta errada [5].
• Como existem $N-1$ pontes, a função Bridge deve ser chamada exatamente $N-1$ vezes. Se o número de chamadas à função Bridge não for $N-1$ no fim da execução da função Solve, o seu programa é considerado como Resposta errada [6].

Avisos importantes

• O seu programa pode implementar outras funções para uso interno ou utilizar variáveis globais.
• O seu programa não deve utilizar a entrada padrão nem a saída padrão. O seu programa não deve comunicar com outros ficheiros por qualquer meio. No entanto, o seu programa pode escrever informações de depuração na saída de erro padrão.

Compilação e execução de teste

Pode descarregar da página da competição um arquivo que contém o avaliador de exemplo para testar o seu programa. O arquivo também contém um ficheiro de código-fonte de exemplo do seu programa.

O avaliador de exemplo é o ficheiro grader.cpp. Para testar o seu programa, coloque grader.cpp, meetings.cpp e meetings.h na mesma pasta e execute o seguinte comando para compilar os programas.

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

Quando a compilação é bem-sucedida, é gerado o ficheiro executável grader.

Note que o avaliador real é diferente do avaliador de exemplo. O avaliador de exemplo é 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}{l} N\\ A_0\ B_0\\ \vdots\\ A_{N-2}\ B_{N-2} \end{array} $$

$A_i$ e $B_i$ ($0 \le i \le N-2$) indicam que as ilhas $A_i$ e $B_i$ estão diretamente ligadas por uma ponte.

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 o seu programa for considerado correto, escreve o número de chamadas à função Query, como em “Accepted: 100”.
• Se o seu programa for considerado como resposta errada, escreve o seu tipo, como em “Wrong Answer [1]”.

Se o seu programa for considerado como vários tipos de resposta errada, o avaliador de exemplo apresenta apenas um deles.

Restrições

Consulte a secção “Entrada do avaliador de exemplo” para a definição de $A_i$ e $B_i$.

• $3 \le N \le 2\,000$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• É possível viajar entre quaisquer ilhas utilizando algumas pontes.
• Cada ilha tem, no máximo, 18 pontes diretamente ligadas a ela.

Subtarefas

1. (7 pontos) $N \le 7$.
2. (10 pontos) $N \le 50$.
3. (12 pontos) $N \le 300$.

4. (71 pontos) Sem restrições adicionais.

5. Nas subtarefas 1, 2 e 3, se o seu programa estiver correto em todos os casos de teste de uma subtarefa, recebe a pontuação completa.

6. Na subtarefa 4, se o seu programa estiver correto em todos os casos de teste, a sua pontuação será a seguinte, sendo $X$ o número máximo de chamadas à função Query num caso de teste.

   • 49 pontos se $40\,000 < X \le 100\,000$, e
   • 71 pontos se $X \le 40\,000$.

Exemplo de comunicação

Segue-se uma entrada de exemplo para o avaliador de exemplo e as chamadas de funções correspondentes.

Entrada 1

5
0 1
0 2
1 3
1 4

Chamadas de exemplo