Você conhece a empresa Just Ordinary Inventions? O trabalho dessa empresa é criar “invenções simplesmente comuns”.

JOI está jogando o jogo mais recente desenvolvido pela Just Ordinary Inventions.

Nesse jogo, explora-se uma masmorra composta de várias salas e caminhos. Cada caminho liga duas salas distintas e pode ser percorrido nos dois sentidos. Existe no máximo um caminho entre quaisquer duas salas distintas, e não há caminhos cujas duas extremidades sejam a mesma sala. Sabe-se também que é possível ir de qualquer sala a qualquer outra usando alguns caminhos. As salas são muito parecidas: salas com o mesmo número de caminhos incidentes são completamente indistinguíveis apenas pela aparência.

Para ajudar o jogador, cada sala tem uma marca de referência e um pedestal. Usando a marca como referência, os caminhos que saem da sala podem ser numerados como primeiro, segundo, e assim por diante. A estrutura da masmorra não muda durante o jogo. Portanto, sair da mesma sala pelo caminho de mesmo número sempre leva à mesma sala. Sobre cada pedestal há uma joia cuja cor o jogador pode mudar. A cor é uma entre as cores $1,2,\ldots,X$; no início do jogo, todas as joias têm a cor $1$. A cor de uma joia só muda quando o jogador a altera.

JOI percebeu que seria fácil concluir o jogo se conhecesse a estrutura da masmorra, isto é, como as salas estão ligadas por caminhos. Porém, apesar de suas tentativas, não conseguiu determinar essa estrutura. Você decidiu escrever um programa para determiná-la em seu lugar.

Tarefa

Escreva um programa que explore a masmorra e determine sua estrutura. Porém, JOI não quer que a estrutura seja totalmente revelada. Assim, em vez de responder diretamente com a estrutura, para cada inteiro $i$ de $1$ a $R$, o programa deve informar quantos pares de salas têm distância mínima de exatamente $i$ caminhos. Trocar a ordem das duas salas não cria um par diferente.

Para explorar a masmorra, você recebe uma biblioteca que permite realizar as seguintes ações.

• Descobrir quantos caminhos saem da sala atual.
• Descobrir a cor da joia no pedestal da sala atual.
• Mudar a cor da joia no pedestal da sala atual para uma cor especificada (que pode ser a mesma cor atual). Em seguida, escolher um caminho que sai da sala e percorrê-lo até outra sala.
• Descobrir o número do último caminho usado entre os caminhos que saem da sala atual.

Detalhes de implementação

Você deve escrever um programa que implemente o método para responder a JOI. O programa deve incluir dungeon2.h.

O programa deve implementar a rotina abaixo.

• void Inspect(int R)

  Essa rotina é chamada uma única vez, no início.

  • O argumento R indica que, para cada inteiro $i$ de $1$ a $R$, você deve informar quantos pares de salas têm distância mínima de exatamente $i$ caminhos. Trocar a ordem das duas salas não cria um par diferente.

Você também deve chamar a rotina abaixo para fornecer as respostas.

• void Answer(int D, int A)

  • Os argumentos D e A indicam que essa chamada informa que existem $A$ pares de salas cuja distância mínima é exatamente $D$ caminhos.

  As chamadas a Answer devem satisfazer as condições abaixo.

  • D deve ser um inteiro de $1$ a $R$. Caso contrário, a resposta será considerada incorreta [1].
  • Não chame Answer duas ou mais vezes com o mesmo argumento D. Caso contrário, a resposta será considerada incorreta [2].
  • Answer deve ser chamada exatamente $R$ vezes. Caso contrário, a resposta será considerada incorreta [3].
  • A deve ser o número de pares de salas cuja distância mínima é exatamente $D$ caminhos. Caso contrário, a resposta será considerada incorreta [4].

  Se uma chamada a Answer for considerada incorreta, não há garantia de que o restante do programa será executado.

Além disso, seu programa pode chamar as rotinas abaixo.

• void Move(int I, int C)

  • O argumento I é o número do caminho que o jogador escolhe para se mover. Imediatamente após essa chamada, o jogador percorre o $I$-ésimo caminho que sai da sala atual até outra sala.
  • O argumento C indica que, antes de mudar de sala, a joia no pedestal da sala atual será alterada para a cor $C$.

  As chamadas a Move devem satisfazer as condições abaixo.

  • Seja $K$ o número de caminhos que saem da sala atual. O argumento I deve ser um inteiro de $1$ a $K$. Caso contrário, a resposta será considerada incorreta [5].
  • Seja $X$ o número de cores possíveis para as joias. O argumento C deve ser um inteiro de $1$ a $X$. O valor de $X$ é definido em cada subtarefa. Caso contrário, a resposta será considerada incorreta [6].
  • Não chame Move mais de $1\,500\,000$ vezes. Caso contrário, a resposta será considerada incorreta [7].

• int NumberOfRoads()

  • Retorna o número de caminhos que saem da sala atual do jogador.

• int LastRoad()

  • Retorna o número do último caminho usado pelo jogador entre os caminhos que saem da sala atual. Se for chamada antes de qualquer chamada a Move, retorna $-1$.

• int Color()

  • Retorna a cor da joia no pedestal da sala atual do jogador.

Após a chamada à rotina Inspect, as respostas serão verificadas.

Você pode implementar outras rotinas para uso interno e declarar variáveis globais. Porém, sua submissão não deve interagir de nenhuma forma com a entrada padrão, a saída padrão ou outros arquivos.

Compilação e execução

Um avaliador de exemplo para testar seu programa está incluído no arquivo compactado disponível no site da competição. Esse arquivo também contém exemplos dos arquivos que devem ser submetidos.

O avaliador de exemplo consiste em um único arquivo, grader.c ou grader.cpp. Para testar seu programa, execute os comandos abaixo.

• Para C

  gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm

• Para C++

  g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

Se a compilação for bem-sucedida, será gerado um executável chamado grader.

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

Entrada do avaliador de exemplo

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

• A primeira linha contém os inteiros $N,X,R$, separados por espaços. Isso significa que a masmorra tem $N$ salas, chamadas sala $1$, sala $2$, ..., sala $N$, que as joias podem ter $X$ cores e que o programa deve fornecer $R$ valores como resposta.
• Na linha $2i-1$ ($1 \le i \le N$) das próximas $2N$ linhas há um inteiro $D_i$, indicando que saem $D_i$ caminhos da sala $i$. A linha $2i$ ($1 \le i \le N$) contém $D_i$ inteiros $T_{i1},T_{i2},\ldots,T_{iD_i}$, separados por espaços. Isso significa que percorrer o $j$-ésimo caminho ($1 \le j \le D_i$) que sai da sala $i$ leva à sala $T_{ij}$.
• A linha $j$ ($1 \le j \le R$) das próximas $R$ linhas contém um inteiro $A_j$. Isso significa que existem $A_j$ pares de salas cuja distância mínima é exatamente $j$ caminhos. Ou seja, para cada $j$ ($1 \le j \le R$), o avaliador de exemplo considera correta a chamada a Answer com $j$ como argumento D e $A_j$ como argumento A, e considera incorretos os outros casos.

O avaliador de exemplo chama a rotina que você implementou com o jogador inicialmente na sala $1$.

Saída do avaliador de exemplo

Se o programa terminar normalmente, o avaliador de exemplo escreve as informações abaixo na saída padrão, em uma única linha (as aspas não são impressas).

• Se a resposta estiver correta, imprime o número de chamadas à função Move, como em Accepted : #move = 8.
• Se a resposta estiver incorreta, imprime o tipo de erro, como em Wrong Answer [1].

Restrições

Todos os dados de entrada satisfazem as condições abaixo. Consulte a seção “Entrada do avaliador de exemplo” para o significado de $N,D_i,T_{ij}$.

• $2 \le N \le 200$.
• $3 \le X \le 100$.
• $1 \le R \le 200$.
• $1 \le D_i \le N-1$ ($1 \le i \le N$).
• $1 \le T_{ij} \le N$ e $T_{ij} \ne i$ ($1 \le i \le N$, $1 \le j \le D_i$).
• $T_{i1},T_{i2},\ldots,T_{iD_i}$ são todos distintos ($1 \le i \le N$).
• Para cada $i,j$ ($1 \le i \le N$, $1 \le j \le D_i$), existe um $k$ ($1 \le k \le D_{T_{ij}}$) tal que $T_{T_{ij}k}=i$.
• É possível ir de qualquer sala a qualquer outra usando alguns caminhos.

Subtarefas

A seguir, sejam $N$ o número de salas e $M$ o número de caminhos da masmorra nos dados de entrada.

Subtarefa 1 [17 pontos]

As condições abaixo são satisfeitas.

• $N \le 50$.
• $M \le 100$.
• $X=100$.

Subtarefa 2 [27 pontos]

As condições abaixo são satisfeitas.

• $N \le 50$.
• $M \le 100$.
• $X=3$.

Subtarefa 3 [56 pontos]

• $X=3$.

Nesta subtarefa, a pontuação é determinada da seguinte forma.

• Seja $L$ o máximo do valor abaixo entre todos os casos de teste desta subtarefa.

  • $C/M$, em que $C$ é o número de chamadas a Move.

• Então, a pontuação desta subtarefa é:

  • $56$ pontos se $L \le 14$.
  • $\lfloor 70-L\rfloor$ pontos se $14<L \le 32$.
  • $\left\lfloor 54-\dfrac{L}{2}\right\rfloor$ pontos se $32<L \le 64$.
  • $0$ pontos se $64<L$.

Aqui, $\lfloor x\rfloor$ denota o maior inteiro que não excede $x$.

No sistema de avaliação, quando o programa termina corretamente e a resposta é considerada correta, aparece Accepted na coluna de detalhes. Porém, na avaliação da subtarefa 3, observe que, para casos de teste em que os valores $C,M$ acima satisfazem $64<C/M$, a coluna de resultado mostra resposta incorreta.

Exemplos

A seguir são apresentados um exemplo de entrada lido pelo avaliador de exemplo e as chamadas de rotinas correspondentes.

Entrada 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

Chamadas de exemplo

Observe que as chamadas de função deste exemplo não são necessariamente significativas.