Caça Ao Tesouro

Esse problema é interativo

Flúcio, habitante da Nlogônia, está brincando de caça ao tesouro com seus amigos. Nesse jogo, seus amigos esconderam um tesouro muito valioso em uma cidade da Nlôgonia, e Flúcio deve encontrá-lo.

A Nlogônia tem um sistema de estradas e cidades bastante peculiar: existem $$n$$ cidades e $$n-1$$ estradas de exatamente $$1$$ quilômetro, sendo que entre qualquer par de cidades existe exatamente um caminho simples de estrada conectando-as.

No entanto, está havendo uma pandemia global, e ele não pode sair de casa, para evitar o contágio. Portanto, ele e seus amigos decidiram uma forma mais consciente de jogarem o jogo: Flúcio pode fazer até $$36 perguntas$$ de dois tipos à seus amigos:

• $$?$$ $$1$$ $$u$$ Seus amigos deverão responder a distância no caminho entre a cidade $$u$$ e a cidade que contem o tesouro.
• $$?$$ $$2$$ $$u$$ Seus amigos deverão responder a segunda cidade no caminho entre a cidade $$u$$ e a cidade que contem o tesouro. Se Flúcio fizer esse tipo de pergunta, onde $$u$$ é a cidade do tesouro, os amigos responderão $$0$$.

Ajude Flúcio a encontrar o tesouro.

Entrada:

A primeira linha de entrada contem um inteiro $$n$$, o número de cidades da Nlogônia.

As próximas $$n-1$$ linhas contém dois inteiros $$u$$ e $$v$$, que denotam que e estrada entre as cidades $$u$$ e $$v$$

Restrições:

• $$1 \leq n \leq 2*1e5$$
• $$1 \leq u, v \leq n$$

Interação:

Você pode fazer até 36 perguntas do tipo: “$$?$$ $$T$$ $$u$$” onde $$T \in \{1, 2 \}$$ e $$1 \leq u \leq n$$, como descrito no enunciado do problema.

Após cada pergunta, o seu programa deverá ler um inteiro, a resposta do problema. Se o seu programa ler $$-1$$, ele imprimiu uma pergunta de formato inválido, ou ultrapassou $$36$$ perguntas, e deve ser terminado imediatamente.

Quando encontrar o tesouro, imprima “!” seguido por um espaço e o número da cidade do tesouro. Isso não conta como uma pergunta, mas pode ser apenas feito uma vez.

Após cada pergunta e após encontrar o tesouro, limpe a tela com um dos seguintes comandos:

• $$fflush(stdout)$$ ou $$cout.flush()$$ em C++
• $$System.out.flush()$$ em Java
• $$flush(output)$$ em Pascal
• $$stdout.flush()$$ em python.

Exemplo:

7
2 1
2 4
3 5
6 2
1 3
2 7

1

3

0

Para submeter sua solução, use esse link.