← 返回题目列表

AtCoder · tupc2023_j

J. 彩色完整图

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

配点 : {100} 点

問題文

这个问题是一个交互问题。

N 完全无向的顶点图 有 G 。完全无向图有什么不同 2 顶点之间有一条无向边。 1 这是一个看起来有两种类型的图表。
每面都被涂成红色或蓝色,但颜色并未显示。

您可能有以下问题: 您最多可以执行 2N 次。 连接

  • 頂点 i 与 边 j \ (1 \leq i , j \leq N, \ i \neq j) 的边 听听 (i,j) 的颜色。

图表 G 的生成树,其中所有边都涂成相同的颜色。 1 请输出一个。
我们可以证明,在问题的约束下,这样的事情必然存在。

但是,答案不包含在提出的问题数量中。

制約

  • 3 \leq N \leq 5 \times 10^4
  • N 是一个整数

入出力

这个问题是一个交互问题。
首先, 交换第N 被赋予标准输入。

N

然后您可以提问。
请按照以下格式将您的问题输出到标准输出(在末尾输入新行)。 请注意,它必须是
1 \leq i , j \leq N,\ i \neq j 。

? i j

如果问题有效,则问题的答案 c 由标准输入给出。 如果

辺 (i,j) 的颜色为红色 R,如果是蓝色 B 。 对于

c

如果问题因问题格式不正确、提问次数超过指定次数等原因被判定为无效问题,将发送一条消息,而不是问题的答案。 F 。 对于

F

此时提交将被判断为错误,判断程序结束。

要输出的生成树 一旦你知道 T , i 第一条边是顶点 u_i 和顶点 v_i ,请按以下格式将您的答案输出到标准输出(在末尾插入换行符)。

!  
u_1 v_1  
u_2 v_2
\vdots  
u_{N-1} v_{N-1}

仅当满足以下所有条件时,答案才是正确的。

  • 1 \leq u_i, v_i \leq N , \ u_i \neq v_i
  • N-1 由书本边和两端顶点组成的图是 这是 G 的生成树。
  • N-1 书的所有面都涂成相同的颜色。

如果收到答案,无论答案正确还是错误,判断程序都会终止。

注意点

  • 每次打印输出时,在末尾添加一个换行符并刷新标准输出。如果不这样做,判断结果将是 TLE 。
  • 如果对话过程中输出错误或程序中途终止,则判断结果不确定。
  • 打印答案后(或F )立即正常终止程序。否则,判断结果不确定。
  • 特别要小心,因为额外的换行符也被视为无效的格式化输出。
  • 我们建议您使用快速方法执行输入/输出。
  • 本题的判断是自适应的。这意味着图的边缘可能会改变颜色而不与约束和先前的输出相矛盾。

入出力例

以下是 N=3 和边缘 (1,2), (2,3) 为红色,边缘 这是 (1,3) 为蓝色图时的交互示例。

入力 出力 説明
3 首先是一个整数 N 。 对于
? 1 2 作为一个问题 听听 (1,2) 的颜色。 因为
R 辺 (1,2) 的颜色是红色 因为 R 。 对于
? 1 3 作为一个问题 听听 (1,3) 的颜色。 因为
B 辺 (1,3) 的颜色是蓝色 B 。 对于
? 2 3 作为一个问题 听听 (2,3) 的颜色。 因为
R 辺 (2,3) 的颜色是红色 因为 R 。 对于
!
1 2
2 3
作为答案 2 书的侧面 输出 (1,2),(2,3) 。
所有面都涂成相同的颜色 由于它是 G 的生成树, AC 。 对于