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.