Neva durante o inverno em muitos lugares da Rússia. Há $N$ cidades na Rússia, numeradas de $0$ a $N-1$, e $N-1$ estradas, numeradas de $0$ a $N-2$. A estrada $i$ ($0 \le i \le N-2$) liga duas cidades distintas $A_i,B_i$ ($0 \le A_i < B_i \le N-1$) nos dois sentidos. É possível viajar entre quaisquer duas cidades distintas passando por algumas estradas.

A situação da neve em cada estrada muda de um dia para outro. Em qualquer dia, em cada estrada está nevando ou não está nevando. Essa situação não muda durante um mesmo dia.

Anya e Boris trabalham no departamento de transportes da Rússia. Anya pertence ao setor que administra informações sobre as estradas, e Boris ao setor que responde a perguntas dos cidadãos. Os cidadãos perguntam qual é o número mínimo de estradas em que está nevando pelas quais precisam passar para viajar da cidade $0$, a capital da Rússia, até alguma outra cidade. Normalmente, depois de receber uma pergunta, Boris se comunica com Anya e responde ao cidadão.

Agora, a Rússia sediará um campeonato mundial de programação durante $Q$ dias. Durante o campeonato, espera-se que as linhas de comunicação fiquem congestionadas, dificultando a comunicação direta entre Anya e Boris. Por isso, eles decidiram se comunicar da seguinte maneira.

• No início de cada dia, Anya recebe as informações sobre a neve daquele dia e envia dados a um servidor intermediário.
• Ao receber uma pergunta de um cidadão, Boris responde comunicando-se com o servidor intermediário.

A comunicação entre Anya e Boris está sujeita às seguintes restrições.

• A capacidade do servidor intermediário é $L=1\,000$ bits. Anya pode armazenar no máximo $L$ bits de informação nele.
• Todos os dados armazenados no servidor intermediário são inicializados com $0$ no início de cada dia.
• Em cada comunicação com o servidor intermediário, Boris pode ler um bit de informação em uma posição especificada.
• Para responder a cada pergunta, Boris pode se comunicar com o servidor intermediário no máximo 20 vezes.

Você conhece o diretor do departamento de transportes e ficou encarregado de elaborar a estratégia de Anya e Boris.

Tarefa

Escreva programas que implementem uma estratégia para Anya e Boris responderem corretamente às perguntas dos cidadãos.

Detalhes de implementação

Você deve enviar dois arquivos na mesma linguagem de programação.

O primeiro arquivo deve se chamar Anya.c ou Anya.cpp. Esse arquivo implementa a estratégia de Anya e deve implementar as duas rotinas abaixo. O programa deve incluir Anyalib.h.

• void InitAnya(int N, int A[], int B[])

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

  • O argumento $N$ representa o número de cidades.
  • Os argumentos A[] e B[] são sequências de comprimento $N-1$ que representam as conexões das estradas. Os elementos A[i] e B[i] ($0 \le i \le N-2$) são inteiros que indicam que a estrada $i$ liga as cidades A[i] e B[i] nos dois sentidos e satisfazem $0 \le \mathrm{A}[i] < \mathrm{B}[i] \le N-1$.

• void Anya(int C[])

  Esta função é chamada $Q$ vezes depois de InitAnya. Ela corresponde à escolha, por Anya, da sequência de bits que será armazenada no servidor intermediário, após a atualização das informações sobre a neve no início de cada dia.

  • O argumento C[] é uma sequência de comprimento $N-1$ que representa as informações sobre a neve nas estradas. O elemento C[i] ($0 \le i \le N-2$) é um inteiro $0$ ou $1$ que representa a situação da estrada $i$: C[i] = 1 indica que está nevando na estrada $i$, e C[i] = 0 indica que não está nevando nela.

  Dentro da função Anya, é possível chamar a seguinte função.

  • void Save(int place, int bit)

    Esta função representa a operação em que Anya armazena um bit no servidor intermediário.

    • O argumento place representa a posição em que o bit será escrito. Deve ser um inteiro de $0$ a $L-1$, inclusive. Se for chamado com um valor fora desse intervalo, o resultado será Resposta Incorreta [1]. Além disso, em cada chamada de Anya, não é permitido chamar essa função duas ou mais vezes com o mesmo argumento place. Se ela for chamada duas vezes com o mesmo argumento, o resultado será Resposta Incorreta [2].
    • O argumento bit é o inteiro que representa o bit a ser escrito e deve ser $0$ ou $1$. Se a função for chamada com qualquer outro valor, o resultado será Resposta Incorreta [3].

  Depois de uma chamada de Save, o conteúdo do bit na posição place do servidor intermediário passa a ser bit.

  Se uma chamada de Save for considerada incorreta, o programa termina imediatamente.

  Imediatamente antes de cada chamada da função Anya, todos os bits do servidor intermediário são sempre inicializados com $0$. Portanto, ao terminar Anya, as posições em que nenhuma escrita foi feita por Save contêm $0$.

O segundo arquivo deve se chamar Boris.c ou Boris.cpp. Esse arquivo implementa a estratégia de Boris e deve implementar as duas rotinas abaixo. O programa deve incluir Borislib.h.

• void InitBoris(int N, int A[], int B[])

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

  • O argumento $N$ representa o número de cidades.
  • Os argumentos A[] e B[] são sequências de comprimento $N-1$ que representam as conexões das estradas. Os elementos A[i] e B[i] ($0 \le i \le N-2$) são inteiros que indicam que a estrada $i$ liga as cidades A[i] e B[i] nos dois sentidos e satisfazem $0 \le \mathrm{A}[i] < \mathrm{B}[i] \le N-1$.

• int Boris(int city)

  Esta função é chamada algumas vezes depois de InitBoris. Ela corresponde à ação de Boris diante de uma pergunta de um cidadão.

  • O argumento city representa a pergunta do cidadão. É um inteiro de $1$ a $N-1$, inclusive. A pergunta é qual o número mínimo de estradas em que está nevando pelas quais é necessário passar para viajar da cidade $0$ até a cidade city.
  • A função Boris deve retornar um inteiro de $0$ a $N-1$, inclusive, que seja a resposta à pergunta. Se retornar um inteiro fora desse intervalo, o resultado será Resposta Incorreta [4]. Se a resposta estiver errada, o resultado será Resposta Incorreta [7].

  Dentro da função Boris, é possível chamar a seguinte função.

  • int Ask(int place)

    Esta função representa a operação em que Boris lê um bit do servidor intermediário.

    • O argumento place representa a posição do bit a ser lido. Deve ser um inteiro de $0$ a $L-1$, inclusive. Se a função for chamada com um valor fora desse intervalo, o resultado será Resposta Incorreta [5].

    O valor retornado por Ask é um inteiro $0$ ou $1$ que representa o conteúdo do bit na posição place do servidor intermediário. Além disso, Ask só pode ser chamada no máximo 20 vezes em cada chamada de Boris. Se esse limite for excedido, o resultado será Resposta Incorreta [6].

  Se uma chamada de Ask for considerada incorreta, o programa termina imediatamente.

Procedimento de avaliação

A avaliação segue o procedimento abaixo. Se o resultado for considerado incorreto, o programa termina imediatamente.

1. Para fornecer as informações sobre as estradas, InitAnya e InitBoris são chamadas uma vez cada, nessa ordem.

2. Para $i=1,\ldots,Q$, realizam-se as seguintes operações, em ordem.

   a. A função Anya é chamada exatamente uma vez. Isso corresponde à escolha, por Anya, dos bits a armazenar no servidor intermediário depois da atualização das informações sobre a neve no início do dia.

   b. A função Boris é chamada $D_i$ vezes, em que $D_i$ é o número de perguntas dos cidadãos no dia $i$. Na $j$-ésima chamada ($1 \le j \le D_i$), o argumento é $R_{ij}$ ($1 \le R_{ij} \le N-1$). Se o valor retornado por Boris nessa chamada não for igual ao número mínimo de estradas em que está nevando pelas quais é necessário passar para viajar da cidade $0$ à cidade $R_{ij}$, a resposta será considerada incorreta.

3. Se nenhuma resposta tiver sido considerada incorreta, o resultado será correto.

Observações importantes

• O tempo de execução e o uso de memória são medidos nas etapas (1) e (2) do Procedimento de avaliação. Se o resultado for correto, na etapa (2) Anya será chamada $Q$ vezes no total e Boris será chamada $D_1+\cdots+D_Q$ vezes no total.
• Anya e Boris não podem conhecer os valores de $D_1,\ldots,D_Q$.
• A função Boris não recebe informação sobre quando a função Anya atualizou os dados armazenados no servidor intermediário.
• É permitido implementar outras rotinas para uso interno ou declarar variáveis globais. Porém, os dois programas enviados são ligados ao avaliador para formar um único executável. Por isso, todas as variáveis globais e rotinas internas de cada arquivo, exceto InitAnya, Anya, InitBoris e Boris, devem ser declaradas static para evitar interferências entre os arquivos. Durante a avaliação, esse programa é executado em dois processos, um para Anya e outro para Boris; portanto, os dois lados não podem compartilhar as variáveis globais do programa.
• 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

O arquivo compactado que pode ser baixado do site da competição contém um avaliador de exemplo para testar seus programas. Ele também contém exemplos dos arquivos que devem ser enviados.

O avaliador de exemplo consiste em um arquivo, grader.c ou grader.cpp. Se seus programas se chamarem Anya.c e Boris.c, ou Anya.cpp e Boris.cpp, execute os seguintes comandos para testá-los.

• Para C

  gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• Para C++

  g++ -std=c++11 -O2 -o grader grader.cpp Anya.cpp Boris.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 é executado como um único processo, que lê a entrada padrão e escreve os resultados na saída padrão.

Visão geral do avaliador de exemplo

O avaliador de exemplo chama as funções de acordo com o Procedimento de avaliação.

Observe que o seguinte comportamento difere do avaliador real.

• O avaliador de exemplo não verifica a condição de Resposta Incorreta [7]; em vez disso, imprime o valor retornado por Boris para cada pergunta.

Entrada do avaliador de exemplo

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

• A primeira linha contém um inteiro $N$, indicando que há $N$ cidades.
• A linha $i+1$ ($0 \le i \le N-2$) das próximas $N-1$ linhas contém os inteiros $A_i,B_i$ separados por um espaço, indicando que a estrada $i$ liga as cidades $A_i$ e $B_i$ nos dois sentidos.
• A linha seguinte contém um inteiro $Q$, indicando que o campeonato dura $Q$ dias.
• A linha $i$ ($1 \le i \le Q$) das próximas $Q$ linhas contém uma string $S_i$ de comprimento $N-1$ e $D_i+1$ inteiros, separados por espaços. $S_i$ representa a situação da neve no dia $i$. Se o caractere $j+1$ da esquerda de $S_i$ ($0 \le j \le N-2$) for 1, está nevando na estrada $j$; se for 0, não está nevando nela. O primeiro dos $D_i+1$ inteiros seguintes é $D_i$. Os próximos $D_i$ inteiros são $R_{i1},\ldots,R_{iD_i}$. Isso indica que a $j$-ésima pergunta ($1 \le j \le D_i$) no dia $i$ trata do número mínimo de estradas em que está nevando pelas quais é necessário passar para viajar da cidade $0$ à cidade $R_{ij}$.

Saída do avaliador de exemplo

O avaliador de exemplo escreve as seguintes informações na saída padrão. (As aspas não são impressas.)

• Se, durante a execução, o resultado for considerado incorreto, o tipo do erro é impresso, por exemplo, Wrong Answer [1], e a execução termina.
• Se nenhuma das $D_i$ chamadas de Boris feitas depois da $i$-ésima chamada de Anya ($1 \le i \le Q$) for considerada incorreta, nesse momento são impressos $D_i$ inteiros em uma linha, separados por espaços. O $j$-ésimo inteiro impresso ($1 \le j \le D_i$) é o valor retornado por Boris com argumento $R_{ij}$.

Se o programa satisfizer várias condições de resposta incorreta, apenas um dos tipos de erro correspondentes será mostrado.

Restrições

Todos os dados de entrada satisfazem as condições abaixo.

• $2 \le N \le 500$.
• $1 \le Q \le 500$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• $1 \le D_j$ ($1 \le j \le Q$).
• $D_1+\cdots+D_Q \le 500$.
• É possível viajar entre quaisquer duas cidades distintas passando por algumas estradas.

Subtarefas

Subtarefa 1 [15 pontos]

• $N \le 20$.

Subtarefa 2 [5 pontos]

• $N \le 100$.

Subtarefa 3 [35 pontos]

As seguintes condições são satisfeitas.

• $A_i=i$ ($0 \le i \le N-2$).
• $B_i=i+1$ ($0 \le i \le N-2$).

Subtarefa 4 [45 pontos]

Não há restrições adicionais.

Exemplos

A seguir, apresentamos uma entrada de exemplo lida pelo avaliador de exemplo e as chamadas de funções correspondentes.

Entrada 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Exemplo de chamadas de rotinas

Observação

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

Nesse caso, os argumentos passados a InitAnya(...), InitBoris(...) e à primeira e à segunda chamada de Anya(...) são os seguintes, respectivamente.