这是一个交互问题。
在加奈子和守矢神社的直接监督下,幻想乡的铁路系统终于完工了。 GSKR(幻想乡铁路)由 $$$n$$$ 个车站组成,并有 $$$m$$$ 双向轨道连接这些车站。第 $$$i$$$ 轨道的长度为 $$$l_i$$$ ($$$1\le l_i\le 10^6$$$)。由于预算限制,尽管两个车站之间可能有不止一条轨道,但铁路系统可能无法连接。
铁路系统的价值定义为其所有轨道的总长度。铁路系统的最大(或最小)容量定义为所有当前功能系统的全跨越森林中的最大(或最小)值。
简而言之,图的全生成林是与给定图具有相同连接性的生成林。
Kanako 的模拟器只能处理不超过 $$$2m$$$ 的查询。模拟器的输入是长度为 $$$m$$$ 的字符串 $$$s$$$,由字符 0 和/或 1 组成。如果 $$$s_i=$$$ 1,模拟器将假定第 $$$i$$$ 轨道功能正常。然后设备将告诉 Kanako 系统在模拟状态下的最大容量。
Kanako 想知道在模拟器的帮助下所有轨道都能正常运行的系统的最小容量。
铁路系统的结构是预先确定的。换句话说,交互器不具有适应性。
输入
输入的第一行也是唯一一行包含两个整数 $$$n,m$$$ ($$$2 \leq n \leq 200$$$, $$$1\le m \le 500$$$) — 车站和轨道的数量。
互动
通过读取 $$$n,m$$$ 开始交互。
要进行查询,请打印“? $$$s$$$”(不带引号,$$$s$$$ 是长度为 $$$m$$$ 的字符串,由字符 0 和/或 1 组成)。然后您应该从标准输入中读取我们的响应——模拟状态下系统的最大容量。
如果您的程序进行了无效查询或已用完尝试次数,则交互器将立即终止,并且您的程序将得到错误答案。
要给出最终答案,请打印“!$$$L$$$”(不带引号,$$$L$$$ 是所有轨道功能正常的系统的最小容量)。请注意,给出此答案不计入 $$$2m$$$ 查询的限制。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
输入的第一行必须包含两个整数 $$$n,m$$$ ($$$2 \leq n \leq 200$$$, $$$1\le m \le 500$$$) — 车站和轨道的数量。
接下来的 $$$m$$$ 输入行必须恰好包含 $$$3$$$ 以空格分隔的整数 $$$u_i$$$, $$$v_i$$$, $$$l_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i\ne v_i$$$, $$$1 \leq l_i \leq 10^6$$$) — 第 $$$i$$$ 个轨道的端点和长度。
示例
输入 #1
5 4 0 5 9 7
输出 #1
? 0000 ? 1110 ? 1111 ? 1101 ! 7
注意
这是示例的图表,满足 $$$l_i=i$$$。