← 返回题目列表

Codeforces · 1142/E

E. 平克·弗洛伊德

中文机器翻译题面 查看原题

这是一项交互式任务。

科学家们即将为 Floyd-Warshall 算法发明一种新的优化,这将使其能够在线性时间内工作。只有一处优化尚未完成。

众所周知,Floyd-Warshall 算法采用具有 $$$n$$$ 个节点的图,并且每对节点之间恰好有一条边。科学家们有了这张图,而且,他们将每条边指向两个可能的方向之一。

为了优化算法,恰好 $$$m$$$ 边缘被着色为粉红色,所有其余边缘被着色为绿色。您知道所有 $$$m$$$ 粉色边缘的方向,但绿色边缘的方向您未知。在一次查询中,您可以向科学家询问恰好一个绿色边缘的方向,但是,您最多可以执行 $$$2 \cdot n$$$ 这样的查询。

你的任务是找到一个节点,从该节点可以通过由相同颜色的边组成的路径到达其他每个节点。请注意,科学家可能撒谎说他们已经事先固定了所有边缘的方向,因此他们的答案可能取决于您的查询。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$0 \le m \le 100\,000$$$) — 节点数和粉色边数。

接下来的 $$$m$$$ 行描述粉色边缘,这些行中的第 $$$i$$$ 包含两个整数 $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — 第 $$$i$$$ 粉色的开始和结束边缘。保证所有无序对 $$$(u_i, v_i)$$$ 是不同的。

互动

要询问节点 $$$a$$$ 和 $$$b$$$ 之间的绿色边缘的方向,请在单行中打印“?”、$$$a$$$ 和 $$$b$$$,并用空格字符分隔。

对此读取一个整数,如果边从 $$$a$$$ 指向 $$$b$$$,则为 $$$1$$$;如果从 $$$b$$$ 指向 $$$a$$$,则为 $$$0$$$。

您最多可以提出 $$$2 \cdot n$$$ 查询,否则您将得到错误答案。

打印查询后,不要忘记输出行尾并刷新输出。否则您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

回答$$$-1$$$而不是$$$0$$$或$$$1$$$表示您进行了无效查询或超出了查询限制。收到$$$-1$$$后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

黑客

Hacks 的格式应如下。

第一行应包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 300$$$, $$$0 \le m \le n \cdot (n - 1) / 2$$$) - 节点数和粉色边数。

接下来的 $$$m$$$ 行应该描述粉色边缘,第 $$$i$$$ 行应该包含 2 个整数 $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$),这意味着有一个粉色边缘$$$a_i$$$ 到 $$$b_i$$$。所有无序对 $$$(a_i, b_i)$$$ 应该是不同的。

接下来的 $$$(n \cdot (n - 1) / 2 - m)$$$ 行应该描述绿色边缘,第 $$$i$$$ 行应该包含两个整数 $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$)),其中表示从 $$$a_i$$$ 到 $$$b_i$$$ 有一条绿色边缘。所有无序的 $$$(a_i, b_i)$$$ 对应该是不同的,并且也应该与粉红色边缘的对不同。

输出

找到答案后,打印“!”以及通过单色路径可以到达所有其他节点的节点的编号。

示例

输入 #1

4 2
1 2
3 4
0
1
1

输出 #1

? 1 3
? 4 2
? 3 2
! 3

注意

在上面的示例中,查询“? 1 3”的答案是 0,所以边从 3 指向 1。查询“? 4 2”的答案是 1,所以边从 4 指向 2。查询“? 3 2”的答案是 1,所以边从 3 指向 2。因此存在从节点 3 到节点 1 和 2 的绿色路径,并且有是从节点 3 到节点 4 的粉红色路径。