Menji，我哋好掛住你！ - 题目

呢題係互動題。

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