Grafo das somas
Este problema é interativo. Se você nunca tiver visto um problema assim antes, cheque o guia de problemas interativos.
Existe uma permutação¹ escondida de tamanho
e um grafo não-direcionado com
vértices e, inicialmente, nenhuma aresta.
Dois tipos de operação podem ser feitas nesse grafo:
- Escolha um
inteiro tal que
. Para todo o par de vértices
em que
, será adicionada uma aresta.
- Pergunte para o par
,
, qual é o menor caminho em arestas entre os vértices
e
. Se não houver nenhum caminho entre
e
a resposta será
, caso contrário a resposta será a menor distância entre
e
Usando no máximo operações (de ambos os tipos) descubra duas possíveis permutações
, a sua resposta será considerada correta se ao menos uma das suas duas respostas for a permutação certa. É permitido responder duas permutações iguais.
1 - Uma permutação de tamanho é um vetor de tamanho
que contém os números de
a
em uma ordem arbitrária. Por exemplo, os vetores
e
são permutações (de tamanho
e
, respectivamente) porém os vetores
e
não são permutações.
Entrada
A primeira linha contém um inteiro (
) que indica a quantidade de casos de teste.
A primeira linha de cada caso de teste apresenta um inteiro (
), o tamanho da permutação e quantidade de vérices do grafo.
É garantido que a soma dos de todos os casos de teste não excede
Interação
A interação para cada caso começa ao ler o inteiro .
Depois, faça no máximo operações:
- Para fazer uma operação do tipo 1, imprima "+
" (sem as aspas). Então leia um inteiro
ou
. Se o inteiro lido for
, a sua operação foi válida, caso contrário seu código deve terminar a execução imediatamente para receber o veredito de Resposta Errada.
- Para fazer uma operação de tipo 2, imprima "?
" (também sem as aspas). Em seguida, leia a resposta da operação. Caso a resposta lida tenha
, o seu código fez uma operação inválida ou ultrapassou o limite de operações e, portanto, deve a execução deve cessar de imediato para receber Resposta Errada.
Para responder quais são as permutações, imprima "!
...
...
" (de novo, sem as aspas), os dois vetores imprimidos devem ser permutações, mesmo que a primeira permutação esteja correta. Seu código deve então ler um inteiro
ou
, se o inteiro for
, a resposta estava errada e o seu código deve retornar para receber o veredito Resposta Errada. Senão, a resposta estava correta e seu código deve seguir para o próximo caso de teste. Responder as permutações não conta como uma operação.
Exemplo