Menji，我們想念你！ - Problem

這是一道互動題。

Menji 迷路了，大家都很想念他。你的任務是找到他！

有一棵由 $n$ 個節點組成的二元樹 $T$，樹 $T$ 的每條邊長度皆為 $1$。Menji 躲在節點 $X$。你知道這棵樹的結構，但你不知道 $X$。

為了找到 $X$，你可以發送信號。你可以選擇一個節點 $u$ 並選擇一個信號強度 $k$，然後從節點 $u$ 發送一個強度為 $k$ 的信號。若 $u$ 與 $X$ 之間的距離不超過 $k$，Menji 就會收到該信號並回傳一個信號，此時你也會收到信號。否則，你什麼也不會收到。

發送信號很慢，而你時間緊迫，因此請在不超過 $40$ 次信號發送內確定 Menji 的位置。

輸入包含多組測試資料。輸入的第一行包含一個整數 $T$（$1 \le T \le 100$），代表測試資料的組數。

對於每組測試資料，第一行包含一個整數 $n$（$2 \le n \le 3 \times 10^4$），代表樹中的節點數量。

第二行包含 $n - 1$ 個整數 $fa_2, fa_3, \dots, fa_n$（$1 \le fa_i < i$），其中 $fa_i$ 是節點 $i$ 在樹上的父節點。樹以節點 $1$ 為根。

保證該樹是一棵二元樹，亦即不存在 $1 < i < j < k \le n$ 使得 $fa_i = fa_j = fa_k$。

若要發送信號，請依下列格式印出單行：

? u k：代表你在節點 $u$ 產生一個強度為 $k$ 的信號。你需要確保 $1 \le u \le n, 0 \le k \le n$。接著你需要讀取一個整數 $o$（$o \in \{0, 1\}$）。若你收到了信號（等價於 $dis(u, X) \le k$），則 $o = 1$，否則 $o = 0$。

若要回報答案，請依下列格式印出單行：

對於每組測試資料，你最多可以發送 $40$ 次信號。回報答案不計入發送信號的次數。

若你發送超過 $40$ 次信號、發送的信號格式有誤，或回報的答案不正確，互動將會結束，且你會獲得 Wrong answer 的評判結果。

請注意，互動器是自適應的（adaptive），這意味著只要與限制條件以及先前查詢的回答保持一致，答案可能會根據你的查詢而改變。

保證所有測試資料中 $n$ 的總和不超過 $3 \times 10^4$。

在印出每一行後，請別忘記輸出換行字元並刷新輸出緩衝區。在 C++ 中可使用 fflush(stdout) 或 cout.flush()，在 Java 中使用 System.out.flush()，在 Python 中使用 stdout.flush() 來刷新串流。

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

QOJ.ac