Na fábrica da JOI Co., Ltd., há $N$ mesas, numeradas de $0$ a $N-1$. Há $N-1$ esteiras transportadoras, numeradas de $0$ a $N-2$. A esteira $i$ ($0\le i\le N-2$) conecta as mesas $A_i$ e $B_i$ e transporta produtos de uma dessas mesas para a outra. Porém, não conseguimos ver o sentido do transporte. Se ignorarmos os sentidos das esteiras, qualquer par de mesas está conectado por uma sequência de esteiras.

IOI-kun é o diretor da fábrica. Como se esqueceu do sentido de transporte de cada esteira, executará várias vezes a seguinte sequência de operações.

1. Escolhe algumas esteiras e inverte seus sentidos de transporte.
2. Escolhe algumas mesas e coloca um produto em cada mesa escolhida.

3. Para cada mesa em que foi colocado um produto, uma das situações seguintes ocorre simultaneamente.

   • Se não houver esteira que transporte produtos a partir dela, nada acontece.
   • Se houver esteiras que transportem produtos a partir dela, o produto da mesa é transportado por uma delas. O produto para no destino dessa esteira e não se move mais.

4. IOI-kun verifica se há um ou mais produtos em cada mesa. Se houver produtos em uma mesa, ele retira todos eles.

5. Para cada esteira cujo sentido foi invertido na operação 1, IOI-kun inverte novamente seu sentido, que volta a ser o original.

IOI-kun quer determinar o sentido original de cada esteira executando a sequência de operações acima no máximo 30 vezes.

Escreva um programa que, dadas as informações sobre as mesas conectadas pelas esteiras, implemente a estratégia de IOI-kun para determinar o sentido original de cada esteira executando essa sequência de operações no máximo 30 vezes.

Detalhes de implementação

Você deve enviar um arquivo.

O arquivo é conveyor.cpp. Ele deve implementar a função a seguir. O programa deve incluir conveyor.h usando a diretiva de pré-processamento #include.

Em conveyor.cpp, deve ser implementada a seguinte função.

• void Solve(int N, std::vector<int> A, std::vector<int> B)

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

• O parâmetro N é o número de mesas $N$.
• Os parâmetros A, B são vetores de comprimento $N-1$, que descrevem as mesas conectadas pelas esteiras.

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

std::vector<int> Query(std::vector<int> x, std::vector<int> y)

Usando esta função, IOI-kun realiza as operações na fábrica.

• O parâmetro x é um vetor de comprimento $N-1$. Para $0\le i\le N-2$, IOI-kun inverte o sentido da esteira $i$ se x[i] = 1, e não o inverte se x[i] = 0.
• O parâmetro y é um vetor de comprimento $N$. Para $0\le j\le N-1$, IOI-kun coloca um produto na mesa $j$ se y[j] = 1, e não coloca produto nela se y[j] = 0.
• Seja z o valor retornado por esta função. Ele é um vetor de comprimento $N$. Para $0\le j\le N-1$, há um ou mais produtos na mesa $j$ se z[j] = 1, e não há produto nela se z[j] = 0.
• O comprimento do vetor x deve ser igual a $N-1$. Se essa condição não for satisfeita, seu programa será julgado como Resposta incorreta [1].
• Cada elemento do vetor x deve ser 0 ou 1. Se essa condição não for satisfeita, seu programa será julgado como Resposta incorreta [2].
• O comprimento do vetor y deve ser igual a $N$. Se essa condição não for satisfeita, seu programa será julgado como Resposta incorreta [3].
• Cada elemento do vetor y deve ser 0 ou 1. Se essa condição não for satisfeita, seu programa será julgado como Resposta incorreta [4].
• A função Query não deve ser chamada mais de 30 vezes. Se for chamada mais de 30 vezes, seu programa será julgado como Resposta incorreta [5].

void Answer(std::vector<int> a)

Usando esta função, IOI-kun informa o sentido original de cada esteira.

• O parâmetro a é um vetor de comprimento $N-1$. Para $0\le i\le N-2$, a esteira $i$ transporta produtos de $A_i$ para $B_i$ se a[i] = 0, e de $B_i$ para $A_i$ se a[i] = 1.
• O comprimento do vetor a deve ser igual a $N-1$. Se essa condição não for satisfeita, seu programa será julgado como Resposta incorreta [6].
• Cada elemento do vetor a deve ser 0 ou 1. Se essa condição não for satisfeita, seu programa será julgado como Resposta incorreta [7].
• Se IOI-kun informar o sentido errado de alguma esteira, seu programa será julgado como Resposta incorreta [8].
• A função Answer deve ser chamada exatamente uma vez. Se for chamada mais de uma vez, seu programa será julgado como Resposta incorreta [9]. Se a função Solve terminar sem que Answer tenha sido chamada, seu programa será julgado como Resposta incorreta [10].

Avisos 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. Não deve se comunicar com outros arquivos por nenhum método. Porém, pode escrever informações de depuração na saída de erro padrão.

Compilação e execução de testes

Você pode baixar da página da competição um arquivo compactado que contém um avaliador de exemplo para testar seu programa. Ele também contém um arquivo de código-fonte de exemplo para seu programa.

O avaliador de exemplo é o arquivo grader.cpp. Para testar seu programa, coloque grader.cpp, conveyor.cpp e conveyor.h no mesmo diretório e execute o comando abaixo para compilar os programas. Como alternativa, você pode executar compile.sh, incluído no arquivo compactado.

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

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

Observe que o avaliador real é diferente do avaliador de exemplo. O avaliador de exemplo é executado em 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\ A_1\ \cdots\ A_{N-2} \\ B_0\ B_1\ \cdots\ B_{N-2} \\ C_0\ C_1\ \cdots\ C_{N-2} \end{array} $$

Para $0\le i\le N-2$, temos $C_i=0$ se a esteira $i$ transporta produtos da mesa $A_i$ para a mesa $B_i$. Caso contrário, temos $C_i=1$.

Saída do avaliador de exemplo

O avaliador de exemplo escreve as seguintes informações na saída padrão (as aspas servem para dar clareza).

• Se seu programa for julgado correto, informa o número de chamadas à função Query como em Accepted: 22.
• Se seu programa for julgado com algum tipo de resposta incorreta, o avaliador de exemplo escreve seu tipo como em Wrong Answer [4].

Se seu programa satisfizer as condições de vários tipos de resposta incorreta, o avaliador de exemplo informa apenas um deles.

No avaliador de exemplo, entre as esteiras que transportam produtos a partir da mesa em que foi colocado um produto, a esteira que transportará esse produto é escolhida de maneira uniforme e aleatória, determinada por números pseudoaleatórios cujos resultados não mudam entre execuções. Para alterar a semente dos números pseudoaleatórios, execute o avaliador de exemplo com um inteiro como primeiro argumento, conforme abaixo.

./grader 2023

Avisos sobre a avaliação

Em alguns casos de teste, o avaliador real é adaptativo. Isso significa que ele não tem uma resposta fixa no início e responde de acordo com as chamadas anteriores à função Query. É garantido que existe pelo menos uma resposta que não contradiz nenhuma das respostas do avaliador.

Restrições

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

• $0\le A_i\le N-1$ ($0\le i\le N-2$).
• $0\le B_i\le N-1$ ($0\le i\le N-2$).
• Se ignorarmos os sentidos das esteiras, qualquer par de mesas está conectado por uma sequência de esteiras.

Subtarefas

1. (1 ponto) $N=2$.
2. (14 pontos) $N=30$.
3. (10 pontos) $N=100\,000$, $A_i=i$ ($0\le i\le N-2$), $B_i=i+1$ ($0\le i\le N-2$).
4. (75 pontos) $N=100\,000$.

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

3
0 2
2 1
1 0

Chamadas de funções de exemplo

Na primeira chamada à função Query, outro valor de retorno possível, além de [1, 0, 0], é [0, 1, 0].

Na segunda chamada à função Query, o produto na mesa $0$ é transportado para a mesa $2$ pela esteira $0$ e para ali. Observe que ele não será transportado para a mesa $1$ pela esteira $1$.

Observe que esta entrada de exemplo não satisfaz as restrições de nenhuma subtarefa.

Entre os arquivos que podem ser obtidos na página da competição, sample-02.txt satisfaz as restrições da Subtarefa 1 e sample-03.txt satisfaz as restrições da Subtarefa 2.