Questo è un problema interattivo.
Menji si è perso e manca a tutti. È tuo compito trovarlo!
C'è un albero binario $T$, composto da $n$ vertici, e ogni arco dell'albero $T$ ha lunghezza $1$. Menji è nascosto nel vertice $X$. Conosci la struttura dell'albero, ma non conosci $X$.
Per trovare $X$, puoi inviare dei segnali. Puoi selezionare un vertice $u$ e un'intensità del segnale $k$, quindi inviare un segnale di intensità $k$ dal vertice $u$. Se la distanza tra $u$ e $X$ non supera $k$, Menji riceverà il segnale e ne invierà uno indietro, che tu riceverai. Altrimenti non riceverai nulla.
L'invio dei segnali è lento e tu hai fretta, quindi determina la posizione di Menji con non più di $40$ segnali.
Protocollo di interazione
L'input contiene più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 100$), il numero di casi di test.
Per ciascun caso di test, la prima riga contiene un intero $n$ ($2 \le n \le 3 \times 10^4$), il numero di vertici nell'albero.
La seconda riga contiene $n - 1$ interi $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), dove $fa_i$ è il padre di $i$ nell'albero. L'albero ha radice nel vertice $1$.
È garantito che l'albero sia un albero binario, cioè non esistono $1 < i < j < k \le n$ tali che $fa_i = fa_j = fa_k$.
Per inviare un segnale, stampa una singola riga nel seguente formato:
? u k: Indica che generi un segnale nel vertice $u$ con intensità $k$. Devi assicurarti che $1 \le u \le n, 0 \le k \le n$. Poi devi leggere un intero $o$ ($o \in \{0, 1\}$). Se hai ricevuto il segnale, o equivalentemente $dis(u, X) \le k$, allora $o = 1$, altrimenti $o = 0$.
Per comunicare la risposta, stampa una singola riga nel seguente formato:
! u: Indica che hai trovato $X = u$. Dopo aver stampato questa riga devi passare al caso di test successivo, oppure terminare se non ce ne sono altri.
Per ciascun caso di test, puoi inviare al massimo $40$ segnali. Comunicare la risposta non conta come invio di un segnale.
Se invii più di $40$ segnali, o il segnale inviato è malformato, o la risposta comunicata è errata, l'interazione terminerà e riceverai il verdetto Wrong answer.
Nota che l'interattore è adattivo, il che significa che la risposta può cambiare in base alle tue query purché rimanga coerente con i vincoli e con le risposte alle query precedenti.
È garantito che la somma di $n$ su tutti i casi di test non superi $3 \times 10^4$.
Dopo aver stampato ogni riga non dimenticare di mandare a capo e svuotare il buffer di output (flush). Puoi usare fflush(stdout) o cout.flush() per C++, System.out.flush() per Java e stdout.flush() per Python.
Esempio
Input di esempio 1
2 7 1 1 2 2 3 3 1 0 0 7 1 1 2 2 3 3 0 1
Output di esempio 1
? 2 1 ? 3 2 ? 4 0 ! 5 ? 2 1 ? 3 0 ! 3