Il s'agit d'un problème interactif.
Menji s'est perdu et il manque à tout le monde. C'est à vous de le retrouver !
On considère un arbre binaire $T$ composé de $n$ sommets, où chaque arête de l'arbre $T$ est de longueur $1$. Menji se cache au sommet $X$. Vous connaissez la structure de l'arbre, mais vous ne connaissez pas $X$.
Pour trouver $X$, vous pouvez envoyer des signaux. Vous pouvez choisir un sommet $u$ et une intensité de signal $k$, puis envoyer un signal d'intensité $k$ depuis le sommet $u$. Si la distance entre $u$ et $X$ n'excède pas $k$, Menji recevra le signal et en renverra un, que vous recevrez à votre tour. Sinon, vous ne recevrez rien.
L'envoi de signaux est lent et vous êtes pressé ; veuillez donc déterminer la position de Menji en envoyant au plus $40$ signaux.
Protocole d'interaction
L'entrée contient plusieurs jeux de tests. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 100$), le nombre de jeux de tests.
Pour chaque jeu de tests, la première ligne contient un entier $n$ ($2 \le n \le 3 \times 10^4$), le nombre de sommets de l'arbre.
La deuxième ligne contient $n - 1$ entiers $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), où $fa_i$ est le parent du sommet $i$ dans l'arbre. L'arbre est enraciné au sommet $1$.
Il est garanti que l'arbre est un arbre binaire, c'est-à-dire qu'il n'existe pas d'indices $1 < i < j < k \le n$ tels que $fa_i = fa_j = fa_k$.
Pour envoyer un signal, affichez une seule ligne au format suivant :
? u k: indique que vous émettez un signal au sommet $u$ avec une intensité $k$. Vous devez vous assurer que $1 \le u \le n, 0 \le k \le n$. Vous devez ensuite lire un entier $o$ ($o \in \{0, 1\}$). Si vous avez reçu le signal en retour, ou de manière équivalente si $dis(u, X) \le k$, alors $o = 1$, sinon $o = 0$.
Pour annoncer la réponse, affichez une seule ligne au format suivant :
! u: indique que vous avez trouvé $X = u$. Après avoir affiché cette ligne, vous devez passer au jeu de tests suivant, ou terminer votre programme s'il n'y en a plus.
Pour chaque jeu de tests, vous pouvez envoyer au plus $40$ signaux. L'annonce de la réponse ne compte pas comme l'envoi d'un signal.
Si vous envoyez plus de $40$ signaux, si le signal envoyé est mal formé ou si la réponse annoncée est incorrecte, l'interaction prendra fin et vous recevrez le verdict Wrong answer.
Notez que l'interacteur est adaptatif, ce qui signifie que la réponse peut changer au fil de vos requêtes tant qu'elle reste cohérente avec les contraintes et les réponses aux requêtes précédentes.
Il est garanti que la somme de $n$ sur l'ensemble des jeux de tests ne dépasse pas $3 \times 10^4$.
Après avoir affiché chaque ligne, n'oubliez pas d'afficher le retour à la ligne et de vider le tampon de sortie (flush). Vous pouvez utiliser fflush(stdout) ou cout.flush() en C++, System.out.flush() en Java et stdout.flush() en Python.
Exemple
Entrée d'exemple 1
2 7 1 1 2 2 3 3 1 0 0 7 1 1 2 2 3 3 0 1
Sortie d'exemple 1
? 2 1 ? 3 2 ? 4 0 ! 5 ? 2 1 ? 3 0 ! 3