310335: CF1819E. Roads in E City

E. Roads in E Citytime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an interactive problem.

As is well known, the city "E" has never had its roads repaired in its a thousand and a half years old history. And only recently the city administration repaired some of them.

It is known that in total in the city "E" there are $n$ intersections and $m$ roads, which can be used in both directions, numbered with integers from $1$ to $m$. The $i$-th road connects intersections with numbers $a_i$ and $b_i$.

Among all $m$ roads, some subset of the roads has been repaired, but you do not know which one. The only information you could get from the city's road services is that you can get from any intersection to any other intersection by driving only on the roads that have been repaired.

You are a young entrepreneur, and decided to organize a delivery service of fresh raw meat in the city "E" (in this city such meat is called "steaks", it is very popular among the locals). You have already recruited a staff of couriers, but the couriers are willing to travel only on repaired roads. Now you have to find out which roads have already been repaired.

The city administration has given you the city for a period of time, so you can make different queries of one of three types:

1. Block the road with the number $x$. In this case, movement on the road for couriers will be forbidden. Initially all roads are unblocked.
2. Unblock the road with the number $x$. In this case, couriers will be able to move on the road $x$ if it is repaired.
3. Try to deliver the order to the intersection with the number $y$. In this case, one of your couriers will start moving from intersection with number $s$ you don't know and deliver the order to intersection with number $y$ if there is a path on unblocked repaired roads from intersection $s$ to intersection $y$. It is guaranteed that intersection $s$ will be chosen beforehand.

Unfortunately, the city is placed at your complete disposal for a short period of time, so you can make no more than $100 \cdot m$ requests.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1\,000$) — the number of test cases. The description of test cases follows.

The first line contains two integers $n$ and $m$ ($2 \le n \le 2\,000$, $n - 1 \le m \le 2\,000$) —the number of intersections and roads in the city "E".

Each of the following $m$ lines describes one road. The $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) — the ends of the $i$-th road. It is guaranteed that no road connects the city to itself, while it is possible that there are several roads between a pair of different intersections.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases does not exceed $2\,000$.

Interaction

Once you have read the description of the test case, you can make queries. Queries can be of three types:

1. "- $x$" ($1 \le x \le m$). In this case the road with the number $x$ is blocked if it has not already been blocked.
2. "+ $x$" ($1 \le x \le m$). In this case the road with the number $x$ is unblocked. Note that road $x$ must be blocked beforehand. All roads are initially unblocked.
3. "? $y$" ($1 \le y \le n$). In this case the jury program chooses some city $s$. If you can get from town $s$ to town $y$ by unblocked repaired roads, the jury program will output $1$, otherwise the jury program will output $0$. Note that city $s$ will be selected before getting information about city $y$, but your previous requests may be taken into account when selecting city $s$.

In total, you can make no more than $100 \cdot m$ queries for each set of input data.

After you have found all repaired roads, output "! $c_1,\ c_2,\ c_3,\ \ldots,\ c_m$", where $c_i$ is $1$ if road $i$ is repaired, and $0$ if road is not repaired. This output will not count in the total number of queries. The jury program will output $1$ if your answer is correct, and $0$ if the answer is not correct. If you received $0$, your program must terminate immediately to receive a Wrong Answer verdict. Otherwise you can get any verdict, because the program will continue reading from the closed stream. If you read $1$, move on to the next test case, or terminate the program if there is none.

Note that you do not have to unblock all roads before outputting the answer. It is guaranteed that all repaired roads are fixed initially and will not be changed by the jury program depending on queries.

After outputting a query or the answer do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

Hacks

You can't do hacks on this problem.

ExampleInput

2
2 2
1 2
2 1


1

0



1

1
3 3
1 2
2 3
3 1


1

1


1

0


1

1

1

1

Output

- 1
? 1

? 2

- 2
+ 1
? 1

! 1 0





- 1
? 2

? 1

- 2
? 3

? 3

+ 1
? 3

? 2

? 1

! 1 1 1

Note

In the first test case, road $1$ was repaired, while road $2$ was not. For the first delivery request, intersection $1$ was selected as $s$, and the path from intersection $1$ to $1$ exists. For the second delivery request, intersection $1$ was selected as $s$. Since the only repaired road was blocked, there was no path between intersections $1$ and $2$. For the third delivery request, intersection $2$ was selected as $s$, the path between intersections $2$ and $1$ exists along road $1$, which is repaired and unblocked.

In the second test case, intersections $1$, $3$, $1$, $2$, $2$, $3$, $1$ were selected as starting intersections for delivery requests.

题目大意：
这是一个交互式问题。城市“E”在其1500年的历史中从未修复过道路，但最近城市管理局修复了一些道路。总共有n个路口和m条道路，道路可以双向通行，编号为1到m。第i条道路连接编号为a_i和b_i的路口。在所有m条道路中，有一部分已经修复，但你不知道是哪些。从城市道路服务部门得到的唯一信息是，你可以通过只行驶在已修复的道路上，从任何路口到达任何其他路口。你是年轻的创业者，决定在城市“E”组织新鲜生肉的配送服务（在当地，这种肉被称为“牛排”，在当地人中非常受欢迎）。你已经招募了快递员，但快递员只愿意在已修复的道路上行驶。现在你必须找出哪些道路已经修复。城市管理局将城市交给你一段时间，所以你可以进行三种不同类型的查询：

1. 封锁编号为x的道路。在这种情况下，快递员将禁止在这条道路上行驶。初始时所有道路都是开放的。
2. 解封编号为x的道路。在这种情况下，如果道路x已修复，快递员将能够在这条道路上行驶。
3. 尝试将订单送达编号为y的路口。在这种情况下，你的一个快递员将从你不知道的编号为s的路口开始移动，并尝试将订单送达编号为y的路口，如果存在一条从路口s到路口y的未封锁且已修复的道路路径。保证路口s将提前被选中。

不幸的是，城市交给你支配的时间很短，所以你最多可以进行100 * m次请求。

输入输出数据格式：
每个测试用例包含多个测试。第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数n和m（2≤n≤2000，n-1≤m≤2000）——城市“E”中的路口和道路数量。

接下来的m行，每行描述一条道路。第i行包含两个整数a_i和b_i（1≤a_i，b_i≤n）——第i条道路的两端。保证没有道路连接城市到自身，但可能有几条道路连接两个不同的路口。

保证所有测试用例的n和m之和不超过2000。

交互：
一旦你读取了测试用例的描述，你就可以进行查询。查询可以是以下三种类型：

1. “- x”（1≤x≤m）。在这种情况下，如果道路x尚未被封锁，则封锁该道路。
2. “+ x”（1≤x≤m）。在这种情况下，如果道路x已被封锁，则解封该道路。注意道路x必须先被封锁。所有道路初始时都是开放的。
3. “? y”（1≤y≤n）。在这种情况下，评审程序将选择一个城市s。如果你可以通过未封锁且已修复的道路从城市s到达城市y，评审程序将输出1，否则输出0。注意城市s将在获得城市y的信息之前被选中，但你之前的请求可能会在选择城市s时被考虑。

对于每组输入数据，你最多可以进行100 * m次查询。

在你找到所有已修复的道路后，输出“! c_1, c_2, c_3, ..., c_m”，其中c_i如果道路i已修复为1，否则为0。这个输出不会计入查询的总数。评审程序将输出1如果你的答案是正确的，如果答案不正确输出0。如果你收到0，你的程序必须立即终止以获得“错误答案”的裁决。否则你可以得到任何裁决，因为程序将继续从已关闭的流中读取。如果你读到1，继续下一个测试用例，如果没有则终止程序。

注意，在输出答案之前你不需要解封所有道路。保证所有已修复的道路初始时是固定的，评审程序不会根据查询改变它们。

在输出查询或答案后，不要忘记输出换行符并刷新输出。否则，你将得到“空闲限制超出”。为此，使用：

- 在C++中：fflush(stdout) 或 cout.flush();
- 在Java中：System.out.flush();
- 在Pascal中：flush(output);
- 在Python中：stdout.flush();
- 对于其他语言，请查阅文档。

不能对这个问题进行黑客攻击。

例：

输入：
2
2 2
1 2
2 1

1

0

1

1
3 3
1 2
2 3
3 1

1

1


1

0


1

1

1

1

输出：

- 1
? 1

? 2

- 2
+ 1
? 1

! 1 0





- 1
? 2

? 1

- 2
? 3

? 3

+ 1
? 3

? 2

? 1

! 1 1 1题目大意： 这是一个交互式问题。城市“E”在其1500年的历史中从未修复过道路，但最近城市管理局修复了一些道路。总共有n个路口和m条道路，道路可以双向通行，编号为1到m。第i条道路连接编号为a_i和b_i的路口。在所有m条道路中，有一部分已经修复，但你不知道是哪些。从城市道路服务部门得到的唯一信息是，你可以通过只行驶在已修复的道路上，从任何路口到达任何其他路口。你是年轻的创业者，决定在城市“E”组织新鲜生肉的配送服务（在当地，这种肉被称为“牛排”，在当地人中非常受欢迎）。你已经招募了快递员，但快递员只愿意在已修复的道路上行驶。现在你必须找出哪些道路已经修复。城市管理局将城市交给你一段时间，所以你可以进行三种不同类型的查询： 1. 封锁编号为x的道路。在这种情况下，快递员将禁止在这条道路上行驶。初始时所有道路都是开放的。 2. 解封编号为x的道路。在这种情况下，如果道路x已修复，快递员将能够在这条道路上行驶。 3. 尝试将订单送达编号为y的路口。在这种情况下，你的一个快递员将从你不知道的编号为s的路口开始移动，并尝试将订单送达编号为y的路口，如果存在一条从路口s到路口y的未封锁且已修复的道路路径。保证路口s将提前被选中。 不幸的是，城市交给你支配的时间很短，所以你最多可以进行100 * m次请求。 输入输出数据格式： 每个测试用例包含多个测试。第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数n和m（2≤n≤2000，n-1≤m≤2000）——城市“E”中的路口和道路数量。 接下来的m行，每行描述一条道路。第i行包含两个整数a_i和b_i（1≤a_i，b_i≤n）——第i条道路的两端。保证没有道路连接城市到自身，但可能有几条道路连接两个不同的路口。 保证所有测试用例的n和m之和不超过2000。 交互： 一旦你读取了测试用例的描述，你就可以进行查询。查询可以是以下三种类型： 1. “- x”（1≤x≤m）。在这种情况下，如果道路x尚未被封锁，则封锁该道路。 2. “+ x”（1≤x≤m）。在这种情况下，如果道路x已被封锁，则解封该道路。注意道路x必须先被封锁。所有道路初始时都是开放的。 3. “? y”（1≤y≤n）。在这种情况下，评审程序将选择一个城市s。如果你可以通过未封锁且已修复的道路从城市s到达城市y，评审程序将输出1，否则输出0。注意城市s将在获得城市y的信息之前被选中，但你之前的请求可能会在选择城市s时被考虑。 对于每组输入数据，你最多可以进行100 * m次查询。 在你找到所有已修复的道路后，输出“! c_1, c_2, c_3, ..., c_m”，其中c_i如果道路i已修复为1，否则为0。这个输出不会计入查询的总数。评审程序将输出1如果你的答案是正确的，如果答案不正确输出0。如果你收到0，你的程序必须立即终止以获得“错误答案”的裁决。否则你可以得到任何裁决，因为程序将继续从已关闭的流中读取。如果你读到1，继续下一个测试用例，如果没有则终止程序。 注意，在输出答案之前你不需要解封所有道路。保证所有已修复的道路初始时是固定的，评审程序不会根据查询改变它们。 在输出查询或答案后，不要忘记输出换行符并刷新输出。否则，你将得到“空闲限制超出”。为此，使用： - 在C++中：fflush(stdout) 或 cout.flush(); - 在Java中：System.out.flush(); - 在Pascal中：flush(output); - 在Python中：stdout.flush(); - 对于其他语言，请查阅文档。 不能对这个问题进行黑客攻击。 例： 输入： 2 2 2 1 2 2 1 1 0 1 1 3 3 1 2 2 3 3 1 1 1 1 0 1 1 1 1 输出： - 1 ? 1 ? 2 - 2 + 1 ? 1 ! 1 0 - 1 ? 2 ? 1 - 2 ? 3 ? 3 + 1 ? 3 ? 2 ? 1 ! 1 1 1