这是一个交互问题。
众所周知,“E”城在其一千多年的历史中从未修过道路。直到最近,市政府才修复了其中一些。
已知城市“E”共有$$$n$$$个十字路口和$$$m$$$条道路,可双向使用,编号为从$$$1$$$到$$$m$$$的整数。第 $$$i$$$ 条道路连接编号为 $$$a_i$$$ 和 $$$b_i$$$ 的交叉路口。
在所有$$$m$$$道路中,部分道路已修复,但您不知道是哪一条。您可以从城市道路服务部门获得的唯一信息是,您只能在已修复的道路上行驶,才能从任何十字路口前往任何其他十字路口。
你是一位年轻的企业家,决定在“E”城市组织新鲜生肉的送货服务(在这个城市这种肉被称为“牛排”,在当地人中很受欢迎)。你已经招募了一批快递员,但快递员只愿意在修好的道路上行驶。现在你必须找出哪些道路已经修好。
城市管理部门已为您提供了该城市一段时间,因此您可以进行以下三种类型之一的不同查询:
1. 封锁编号为 $$$x$$$ 的道路。在这种情况下,快递员将被禁止在路上行驶。最初,所有道路均畅通。
2. 疏通编号为$$$x$$$的道路。在这种情况下,如果修好了,快递员将能够在路上移动$$$x$$$。
3. 尝试将订单配送到编号为$$$y$$$的路口。在这种情况下,如果在畅通无阻的修复道路上存在从路口 $$$s$$$ 到路口 $$$y$$$ 的路径,您的一名快递员将从您不知道的编号为 $$$s$$$ 的路口开始移动,并将订单递送至编号为 $$$y$$$ 的路口。保证会预先选择交集$$$s$$$。
不幸的是,这座城市在短时间内完全由您支配,因此您只能提出不超过 $$$100 \cdot m$$$ 的请求。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1\,000$$$) — 测试用例的数量。测试用例的描述如下。
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2\,000$$$, $$$n - 1 \le m \le 2\,000$$$) – 城市“E”中的交叉口和道路的数量。
以下 $$$m$$$ 行描述一条道路。这些行中的第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — 第 $$$i$$$ 条道路的末端。可以保证没有道路将城市与其本身连接起来,但在一对不同的交叉路口之间可能存在多条道路。
保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2\,000$$$。
互动
阅读完测试用例的描述后,您可以进行查询。查询可以分为三种类型:
1.“- $$$x$$$”($$$1 \le x \le m$$$)。在这种情况下,如果编号为 $$$x$$$ 的道路尚未被封锁,则该道路将被封锁。
2.“+ $$$x$$$”($$$1 \le x \le m$$$)。在这种情况下,编号为 $$$x$$$ 的道路畅通。请注意,道路 $$$x$$$ 必须事先封锁。所有道路最初都畅通无阻。
3.“?$$$y$$$”($$$1 \le y \le n$$$)。在这种情况下,评审团会选择某个城市$$$s$$$。如果您可以通过畅通无阻的修复道路从城镇$$$s$$$到达城镇$$$y$$$,陪审团程序将输出$$$1$$$,否则陪审团程序将输出$$$0$$$。请注意,将在获取有关城市 $$$y$$$ 的信息之前选择城市 $$$s$$$,但在选择城市 $$$s$$$ 时可能会考虑您之前的请求。
总共,您可以对每组输入数据进行不超过 $$$100 \cdot m$$$ 的查询。
找到所有已修复的道路后,输出“!$$$c_1,\ c_2,\ c_3,\ \ldots,\ c_m$$$”,其中$$$c_i$$$如果道路$$$i$$$已修复则为$$$1$$$,如果道路未修复则为$$$0$$$。此输出不会计入查询总数。如果您的答案正确,陪审团程序将输出 $$$1$$$,如果答案不正确,则输出 $$$0$$$。如果您收到 $$$0$$$,您的程序必须立即终止才能收到错误答案判决。否则你可以获得任何结论,因为程序将继续从关闭的流中读取。如果您读到 $$$1$$$,请继续进行下一个测试用例,或者如果没有则终止程序。
请注意,在输出答案之前,您不必疏通所有道路。保证所有已修复的道路均已初步修复,并且评审团程序不会根据查询进行更改。
输出查询或答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
你无法解决这个问题。
示例
输入 #1
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 ? 1 ? 2 - 2 + 1 ? 1 ! 1 0 - 1 ? 2 ? 1 - 2 ? 3 ? 3 + 1 ? 3 ? 2 ? 1 ! 1 1 1
注意
在第一个测试用例中,道路 $$$1$$$ 已修复,而道路 $$$2$$$ 未修复。对于第一个投递请求,交集$$$1$$$被选为$$$s$$$,并且存在从交集$$$1$$$到$$$1$$$的路径。对于第二个交付请求,交集 $$$1$$$ 被选择为 $$$s$$$。由于唯一修复的道路被封锁,$$$1$$$ 和 $$$2$$$ 十字路口之间没有道路。对于第三次配送请求,路口$$$2$$$被选择为$$$s$$$,路口$$$2$$$和$$$1$$$之间的路径存在于道路$$$1$$$上,该道路已修复且畅通。
在第二个测试用例中,选择路口 $$$1$$$、$$$3$$$、$$$1$$$、$$$2$$$、$$$2$$$、$$$3$$$、$$$1$$$ 作为递送请求的起始路口。