CF1142E Pink Floyd

这是一个交互式任务。 科学家们即将发明一种针对 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$。保证所有无序对 $(u_i, v_i)$ 都互不相同。

当你找到答案时，输出 "! 节点编号"，其中节点编号为从该节点出发可以通过同色路径到达所有其他节点的编号。 ## 交互说明 若要询问节点 $a$ 和 $b$ 之间绿色边的方向，输出 "? $a$ $b$"（用空格分隔）。 你将读入一个整数作为回答，若为 $1$，表示边从 $a$ 指向 $b$；若为 $0$，表示边从 $b$ 指向 $a$。 你最多可以询问 $2 \cdot n$ 次，否则将收到 Wrong Answer 判定。 每次输出询问后不要忘记换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请参考相关文档 如果收到 $-1$ 作为回答，表示你的询问无效或超出了询问次数限制。收到 $-1$ 后应立即退出，否则会收到 Wrong Answer 判定。否则你的程序可能会继续从已关闭的流中读取，导致不可预期的判定。 ## Hack 格式 Hack 数据格式如下： 第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 300$，$0 \le m \le 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)$ 互不相同。 接下来的 $(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 3"，答案是 $0$，表示边从 $3$ 指向 $1$。对于查询 "? 4 2"，答案是 $1$，表示边从 $4$ 指向 $2$。对于查询 "? 3 2"，答案是 $1$，表示边从 $3$ 指向 $2$。因此，存在从节点 $3$ 出发，通过绿色路径到达节点 $1$ 和 $2$，并且存在从节点 $3$ 出发通过粉色路径到达节点 $4$。 由 ChatGPT 4.1 翻译