CF1819E Roads in E City

**这是一道交互题**。 给定一张 $n$ 个点 $m$ 条边的无向连通图，无自环，但可能有重边。 图上有一些特殊边，保证任意两个结点通过特殊边连通，你希望求出所有特殊边。 初始所有边都没有被堵住。你可以进行以下三种操作： - $-\ x$（$1\leq x\leq m$）：如果第 $x$ 条边没有被堵住，则堵住该边。 - $+\ x$（$1\leq x\leq m$）：取消堵住第 $x$ 条边。操作前第 $x$ 条边必须被堵住。 - $?\ y$（$1\leq y\leq n$）：交互库选择某个 $s$ 并返回能否从 $s$ 出发走没有被堵住的特殊边到 $y$。$s$ 可以根据之前的操作而改变，但不会根据本次你选择的 $y$ 而改变。 你最多进行 $100m$ 次操作。 得到答案后，输出 $!\ c_1\ c_2\ \cdots\ c_m$，其中 $c_i$ 表示第 $i$ 条边是否为特殊边。交互库会返回 $0$ 表示答案错误，你必须立刻结束程序，或 $1$ 表示答案正确。 本题有多组数据。 $2\leq n\leq 2000$，$n - 1\leq m\leq 2000$，$1\leq t\leq 1000$，$\sum n, \sum m\leq 2000$。保证图无自环且连通。 翻译贡献者：[Alex_Wei](https://www.luogu.com.cn/user/123294)。

第一行一个正整数 $t$。 对于每组数据，第一行两个正整数 $n, m$。 接下来 $m$ 行，每行两个正整数 $a_i, b_i$（$a_i\neq b_i$）表示第 $i$ 条边。

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. HacksYou can't do hacks on this problem.

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.