Este é um problema interativo.

Neste festival repleto de aromas doces, a preparação da sobremesa que encerra a festa — o leite de dupla película — deparou-se com uma última dificuldade.

Como a sobremesa mais popular da loja, um leite de dupla película perfeito exige uma combinação perfeita entre o bolo da camada superior e o pudim da camada inferior. Neste mágico reino das pulgas, as energias dos elementos das duas camadas de sobremesa entrelaçam-se, escondidas numa complexa rede de cidades.

Os dois experientes mestres de sobremesas da loja — dacake8 e dapudding8 — decidiram pôr-te à prova. Esconderam o bolo e o pudim, respetivamente, nas estradas entre as cidades. Só consultando-os e identificando corretamente uma cidade ligada à loja principal onde te encontras (cidade $1$) por uma estrada que contém uma sobremesa poderás concluir esta sobremesa final de leite de dupla película!

Existem $n$ cidades, com uma estrada a ligar cada par de cidades. Existem $n-1$ pedaços de bolo; o $i$-ésimo está na estrada que liga as cidades $u_{i,1}$ e $v_{i,1}$. Existem $n-1$ pedaços de pudim; o $i$-ésimo está na estrada que liga as cidades $u_{i,2}$ e $v_{i,2}$. As estradas que contêm bolo e as estradas que contêm pudim formam, respetivamente, duas árvores.

Inicialmente, não conheces as posições exatas do bolo e do pudim. Podes fazer, no máximo, $\min(1000,\frac{n\times(n-1)}{2})$ consultas a dacake8 e dapudding8:

• Consultas dacake8 e dapudding8 sobre as cidades $u$ e $v$. Inicialmente, o multiconjunto $S$ está vazio.

  • dacake8 parte da cidade $u$, segue o caminho cujas estradas contêm bolo até chegar à cidade $v$ e acrescenta a $S$ os números das cidades por onde passa.
  • dapudding8 parte da cidade $u$, segue o caminho cujas estradas contêm pudim até chegar à cidade $v$ e acrescenta a $S$ os números das cidades por onde passa.
• A biblioteca de interação devolve o multiconjunto $S$.

Encontras-te na cidade $1$. Depois das consultas, deves indicar uma cidade $u$ tal que a estrada que liga a cidade $1$ à cidade $u$ contenha um tipo de sobremesa.

dacake8 e dapudding8 não querem dificultar-te a tarefa e garantem que as posições do bolo e do pudim já estão fixadas antes das consultas. Por outras palavras, a biblioteca de interação não é adaptativa.

Detalhes de implementação

Não precisas de implementar a função main, nem deves fazê-lo.

Deves incluir o cabeçalho milk.h no ficheiro-fonte milk.cpp e implementar as duas funções seguintes:

void init(int c, int t);

• $c,t$ representam, respetivamente, o número da subtarefa e o número de casos de teste. $id=0$ indica que o teste é um exemplo.
• Para cada teste, a biblioteca de interação chama esta função exatamente uma vez, quando o programa começa a executar.

int find(int c, int n);

• $c,n$ representam, respetivamente, o número da subtarefa e o número de cidades.
• Esta função deve devolver um inteiro positivo $u$, indicando uma cidade $u$ tal que a estrada que liga a cidade $1$ à cidade $u$ contenha um tipo de sobremesa.
• Para cada teste, a biblioteca de interação chama esta função exatamente $t$ vezes.

Podes fazer uma consulta chamando a função seguinte:

std::vector<int>query(int u, int v);

• $u,v$ indicam as duas cidades $u$ e $v$ fornecidas.
• Deves garantir que $1\le u,v\le n$ e $u\ne v$.
• Esta função devolve o multiconjunto $S$, cujo significado é descrito no enunciado.
• Se o tamanho do multiconjunto $S$ for $m$, então $1\le S_i\le n$ e $S_0\le S_1\le \ldots \le S_{m-1}$.
• Deves garantir que, em cada chamada da biblioteca de interação a find, esta função seja chamada, no máximo, $1000$ vezes.

Como testar o programa

Coloca milk.cpp, milk.h e o ficheiro grader.cpp dos anexos no mesmo diretório e compila com C++17:

g++ grader.cpp milk.cpp -o milk -O2 -std=c++17
./milk < ex_milk1.in

Para o executável milk obtido pela compilação:

A primeira linha da entrada da biblioteca de interação contém dois inteiros não negativos $id,t$, que representam, respetivamente, o número do teste e o número de casos de teste.

Para cada caso de teste, a primeira linha contém um inteiro positivo $n$, que representa o número de cidades. Cada uma das linhas $2\sim n$ contém dois inteiros positivos $u_{i,1}$, $v_{i,1}$; cada uma das $n-1$ linhas seguintes contém dois inteiros positivos $u_{i,2}$, $v_{i,2}$.

Se as respostas das $t$ chamadas a find estiverem todas corretas, a biblioteca de interação escreve Correct! na primeira linha e Max queries used: Q na segunda, em que $Q$ representa o maior número de chamadas a query entre todos os casos de teste. Se pelo menos uma resposta estiver errada, escreve Wrong answer.; se uma chamada à interface for inválida, também indica a causa do erro no fluxo de erro padrão.

Exemplos

Entrada 1

0 3
5
1 5
2 5
2 4
3 5
1 2
1 4
3 4
4 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 7
2 4
3 6
4 6
5 7
5 8
6 8
2
1 2
1 2

Saída 1

Correct!
Max queries used: 28

Nota

Atenção: os dados de teste finais não incluem o exemplo.

Nas figuras, uma aresta vermelha indica que a estrada entre as duas cidades contém um pedaço de bolo, e uma aresta azul indica que contém um pedaço de pudim.

Para o primeiro caso de teste, as árvores formadas pelas estradas que contêm bolo e pudim têm a seguinte forma:

Para o segundo caso de teste, as árvores formadas pelas estradas que contêm bolo e pudim têm a seguinte forma:

No terceiro caso de teste, uma estrada pode conter simultaneamente bolo e pudim.

Restrições

Propriedade especial $\text{A}$: as posições do bolo e do pudim são geradas de forma inteiramente aleatória.

Propriedade especial $\text{B}$: é garantido que existe uma única resposta possível.

Propriedade especial $\text{C}$: se ambas as árvores formadas pelas estradas que contêm bolo e pudim forem enraizadas na cidade $1$ e, em cada árvore, forem adicionadas arestas dirigidas de cada cidade para a sua cidade pai, o grafo dirigido resultante será um DAG.

Propriedade especial $\text{D}$: se ambas as árvores formadas pelas estradas que contêm bolo e pudim forem enraizadas na cidade $2$ e, em cada árvore, forem adicionadas arestas dirigidas de cada cidade para a sua cidade pai, o grafo dirigido resultante será um DAG.

Propriedade especial $\text{E}$: as posições do pudim são geradas de forma inteiramente aleatória. As posições do bolo não dependem das posições do pudim.

Propriedade especial $\text{F}$: as duas árvores formadas pelas estradas que contêm bolo e pudim são dois caminhos, ambos com a cidade $1$ numa das extremidades iniciais.

Neste problema, gerar uma árvore aleatoriamente significa utilizar uma sequência de Prufer aleatória.

Pontuação

Se a resposta devolvida por find estiver incorreta ou se os parâmetros de query forem inválidos, o multiplicador da pontuação desse teste será $0$.

Para as subtarefas $1,2,3$, se o número de consultas exceder $\frac{n\times(n-1)}{2}$, o multiplicador da pontuação desse teste será $0$; caso contrário, será $1$.

Para as subtarefas $4\sim 15$, seja $Q$ o maior número de chamadas a query entre todos os casos de teste. O multiplicador da pontuação $f(Q)$ é calculado de acordo com a tabela seguinte:

A pontuação final de um teste é o produto dos pontos desse teste pelo multiplicador da pontuação, com três casas decimais, de acordo com as regras de pontuação real da UOJ.

Limite de tempo: $20\ \mathrm{s}$.

Limite de memória: $512\ \mathrm{MiB}$.