AT_tupc2023_j.Colored Complete Graph

本题为交互式题目。

有一个包含 $N$ 个顶点的完全无向图 $G$。完全无向图指的是对于任意两个不同的顶点之间都有且只有一条无向边的图。
每条边被染成红色或蓝色，但具体的颜色未知。

你最多可以进行 $2N$ 次如下的询问：

• 询问连接顶点 $i$ 与顶点 $j$ 的边 $(i, j)$ 的颜色，其中 $1 \leq i, j \leq N,\ i \neq j$。

请输出图 $G$ 的一棵全域树（即生成树），并且树上的所有边都要是同一种颜色。
在本题约束下，保证一定存在这样的生成树。

注意，回答输出内容不计入询问次数。

本题为交互式题目。
首先，标准输入给出 $N$。

$N$

接下来，你可以进行询问。
每次询问，在标准输出输出如下格式（末尾需要换行并刷新输出）：
注意必须满足 $1 \leq i, j \leq N, \ i \neq j$。

? $i$ $j$

如果询问合法，则该边的颜色 $c$ 将在标准输入中给出。

• 如果边 $(i, j)$ 为红色，输入为 R；为蓝色，则为 B。

$c$

若询问格式不合法、或超出规定次数，则输入为 F。
此时，判为不正确提交，程序会终止。

F

当你已经得到了满足要求的全域树 $T$，则输出你选出的 $N-1$ 条边，每条边用两个顶点表示，全部在一行输出，仍需末尾换行。

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

当且仅当以下全部满足时，判为正确：

• $1 \leq u_i, v_i \leq N,\, u_i \neq v_i$
• $N-1$ 条边以及涉及的顶点构成的图是 $G$ 的一棵全域树
• $N-1$ 条边全都为同一种颜色

答案输出后（或收到 F 后），你的程序应立即正常退出，否则判为不正确。

无输入，无输出。

注意事项

• 每次输出后记得换行并及时刷新 stdout，否则可能因超时（TLE）而被判为错误。
• 交互中输出格式错误，或程序中途退出，判题结果未定义。
• 输出答案（或收到 F）后请迅速正常结束程序，否则结果未定义。
• 特别提醒，额外的换行同样会被判为格式错误。
• 建议使用高效的输入输出方法。
• 本题采用自适应测试：也就是说，边的颜色在不与之前询问矛盾的情况下可能会随着交互改变。

输入输出样例

以下为 $N=3$，$(1,2),(2,3)$ 为红色，$(1,3)$ 为蓝色的例子。

输入	输出	说明
3		首先输入 $N$。
	? 1 2	询问边 $(1,2)$ 的颜色。
R		得到边 $(1,2)$ 为红色。
	? 1 3	询问边 $(1,3)$ 的颜色。
B		得到边 $(1,3)$ 为蓝色。
	? 2 3	询问边 $(2,3)$ 的颜色。
R		得到边 $(2,3)$ 为红色。
	! 1 2 2 3	输出用红色边的全域树。
		输出完毕后立刻退出。

上述输出 $(1,2),(2,3)$ 这两条边作为全域树，且颜色统一，因此判为正确。

数据范围

• $3 \leq N \leq 5 \times 10^4$
• $N$ 为整数。

由 ChatGPT 5 翻译