Object Identification
Contest: Codeforces Round 1004 (Div. 1)
Difficulty rating: 1400
Tags: graphs, greedy, implementation, interactive

This is an interactive problem.

You are given an array $$$x_1, \ldots, x_n$$$ of integers from $$$1$$$ to $$$n$$$. The jury also has a fixed but hidden array $$$y_1, \ldots, y_n$$$ of integers from $$$1$$$ to $$$n$$$. The elements of array $$$y$$$ are unknown to you. Additionally, it is known that for all $$$i$$$, $$$x_i \neq y_i$$$, and all pairs $$$(x_i, y_i)$$$ are distinct.

The jury has secretly thought of one of two objects, and you need to determine which one it is:

- Object A: A directed graph with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, and with $$$n$$$ edges of the form $$$x_i \to y_i$$$.
- Object B: $$$n$$$ points on a coordinate plane. The $$$i$$$-th point has coordinates $$$(x_i, y_i)$$$.

To guess which object the jury has thought of, you can make queries. In one query, you must specify two numbers $$$i, j$$$ $$$(1 \leq i, j \leq n, i \neq j)$$$. In response, you receive one number:

- If the jury has thought of Object A, you receive the length of the shortest path (in edges) from vertex $$$i$$$ to vertex $$$j$$$ in the graph, or $$$0$$$ if there is no path.
- If the jury has thought of Object B, you receive the Manhattan distance between points $$$i$$$ and $$$j$$$, that is $$$|x_i -x_j| + |y_i - y_j|$$$.

You have $$$2$$$ queries to determine which of the objects the jury has thought of.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

Interaction format:
The interaction begins with reading $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the length of the arrays $$$x$$$ and $$$y$$$ at the start of each test case.

Next, read $$$n$$$ integers: $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq n$$$) — the elements of array $$$x$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

The array $$$y_1, y_2, \ldots, y_n$$$ is fixed for each test case. In other words, the interactor is not adaptive.

It is guaranteed that $$$x_i \neq y_i$$$ for all $$$1 \leq i \leq n$$$, and all pairs $$$(x_i, y_i)$$$ are distinct.

To make a query, output "? $$$i$$$ $$$j$$$" (without quotes, $$$1 \le i, j \le n, i \neq j$$$). Then you must read the response to the query, which is a non-negative integer.

To give an answer, output "! A" if Object A is hidden or "! B" if Object B is hidden (without quotes). Note that printing the answer does not count as one of the $$$2$$$ queries.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will reveive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.  Note that if the query is correct, the response will never be $$$-1$$$.

Hacks

The first line must contain an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case must contain an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the length of the hidden array.

The second line of each test case must contain $$$n$$$ integers — $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le n$$$).

The third line of each test case must contain $$$n$$$ integers — $$$y_1, y_2, \ldots, y_n$$$ ($$$1 \le y_i \le n$$$).

It must be ensured that $$$x_i \neq y_i$$$ for all $$$1 \le i \le n$$$, and all pairs $$$(x_i, y_i)$$$ must be distinct.

The fourth line must contain one character: A or B, indicating which of the objects you want to hide.

The sum of $$$n$$$ across all test cases must not exceed $$$2 \cdot 10^5$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$x = [2,2,3]$$$, $$$y = [1,3,1]$$$ and Object A is guessed.

In the second test case, $$$x = [5,1,4,2,3]$$$, $$$y = [3,3,2,4,1]$$$ and Object B is guessed.

Example input:
2
3
2 2 3

1

0

5
5 1 4 2 3

4

4

Example output:
? 2 3

? 1 2

! A

? 1 5

? 5 1

! B

Editorial:
Note that if Object A is chosen, we can receive the number $$$0$$$ in response to some query, while if Object B is chosen, we cannot: since $$$(x_i,y_i) \neq (x_j,y_j)$$$.
If the array $$$x_1, x_2, \ldots, x_n$$$ is not a permutation of the numbers from $$$1$$$ to $$$n$$$, then there will be some number $$$1 \leq a \leq n$$$ that is not present in the array $$$x$$$. In this case, if Object A is chosen, any query $$$(a, *)$$$ will yield a response of $$$0$$$, since there are simply no edges from vertex $$$a$$$ (here $$$*$$$ denotes any number from $$$1$$$ to $$$n$$$ that is not equal to $$$a$$$). We can make such a query, and by checking whether the response is $$$0$$$, we can immediately determine which object the jury has chosen.
However, if the array $$$x_1, x_2, \ldots, x_n$$$ is a permutation. Let's find such $$$i$$$ and $$$j$$$ that $$$x_i=1$$$ and $$$x_j=n$$$, and make the queries $$$(i,j)$$$ and $$$(j,i)$$$. In the case that Object B is chosen: we should receive two identical numbers, both of which must be $$$\geq n-1$$$, since $$$|x_i-x_j| = n-1$$$. It is not hard to see that such a situation is impossible if Object A is chosen: for $$$n \geq 3$$$, in a directed graph with $$$n$$$ vertices and $$$n$$$ edges, it cannot be that for some pair of vertices, the distances from one to the other in both directions are $$$\geq n-1$$$. Therefore, these two queries are sufficient to uniquely identify the objects. If both received numbers are equal and $$$\geq n-1$$$: Object B is chosen; otherwise, Object A is chosen.