Tournament

题目类型：交互题（Hydro 封装交互）
时间限制：60 秒（Hydro 封装推荐；原题为 3 秒）
空间限制：512 MB（Hydro 封装推荐；原题为 256 MB）

本题在原比赛中是交互题。为了放到 Hydro OJ 上测评，本配置包使用 runner.cpp 同时启动选手程序和官方 interactor.cpp，选手仍按交互题方式写程序，通过标准输入输出与评测端交互。

题目描述

有一个隐藏的 $n$ 个顶点的竞赛图，顶点编号为 $1$ 到 $n$。

竞赛图是一个有向图，满足：对于任意两个不同顶点 $u$ 和 $v$，它们之间恰好有一条有向边，方向要么是 $u \to v$，要么是 $v \to u$。

你只知道顶点个数 $n$。一次询问可以询问任意两个不同顶点之间边的方向。

如果一个顶点的出边数量至多为 $1$，则称这个顶点为 好顶点。

你的任务是在不超过 $2000$ 次询问内，找到任意一个好顶点，或者判断不存在好顶点。

交互格式

一次交互包含多组测试数据。

首先，你的程序需要读入两个整数 $g$ 和 $t$：

• $g$ 表示测试组编号；
• $t$ 表示本次交互中的测试数据组数，满足 $1 \le t \le 100$。

接下来对每组测试数据进行一次完整交互。

单组测试数据的交互过程

首先，你的程序读入一个整数 $n$，表示隐藏图的顶点数：

$$1 \le n \le 500$$

随后，你可以进行询问。

一次询问格式为：

? u v

其中 $1 \le u,v \le n$ 且 $u \ne v$。

如果边的方向是 $u \to v$，评测程序会返回：

forward

如果边的方向是 $v \to u$，评测程序会返回：

backward

每组测试数据最多可以询问 $2000$ 次。

当你要输出答案时，输出：

! u

其中：

• 若 $1 \le u \le n$，表示你认为 $u$ 是一个好顶点；
• 若 $u=-1$，表示你认为不存在好顶点。

如果答案正确，评测程序会返回：

OK

此时你的程序应立即处理下一组测试数据，或者在所有测试数据处理完后结束。

如果答案错误，评测程序会返回：

WRONG

此时你的程序应立即终止。

输出刷新说明

如果你使用如下方式输出，一般会自动刷新：

• C++：cout << ... << endl；
• Java：System.out.println；
• Python：print；
• Pascal：writeln。

如果使用其他输出方式，请手动刷新输出流。例如 C++ 中可以使用：

fflush(stdout);

或者：

cout.flush();

注意每次输出询问或答案后都应输出换行。

样例交互

下面给出一个交互过程示例。注意，交互题的样例不是普通输入输出样例，而是展示选手程序与评测程序之间的对话。

评测程序输出给选手程序

0 2
3

forward

backward

OK
5

forward

forward

backward

backward

forward

forward

backward

forward

forward

forward

OK

选手程序输出给评测程序

? 1 2

? 3 2

! 3


? 1 2

? 1 3

? 1 4

? 1 5

? 2 3

? 2 4

? 2 5

? 3 4

? 3 5

? 4 5

! -1

样例解释

在第一组测试数据中，评测程序不是自适应的，隐藏图已经确定。

此处有一张三点竞赛图示意图：顶点 $1,2,3$，边方向为 $1 \to 2$、$1 \to 3$、$2 \to 3$。

因此，询问 ? 1 2 时，评测程序返回 forward，因为边方向为 $1 \to 2$；询问 ? 3 2 时，评测程序返回 backward，因为边方向为 $2 \to 3$。

此时顶点 $2$ 和顶点 $3$ 是好顶点，而顶点 $1$ 不是。因此，输出 ! 3 后，评测程序返回 OK。

在第二组测试数据中，每个顶点都有多条出边，所以不存在好顶点。输出 ! -1 后，评测程序返回 OK。

评分方式

测试数据分为 10 个计分组。只有通过某个组内全部测试点，并满足其依赖组要求时，才能获得该组分数。

本题评测程序有两种行为方式：

1. 非自适应（Non-adaptive）：隐藏图结构在交互开始前固定，不会根据你的询问改变。
2. 自适应（Adaptive）：隐藏图可以在交互过程中变化，但始终保证至少存在一张图与已经回答过的所有询问相符。此时，只有当你的答案对所有可能相符的图都正确时，才算正确。

组别	分数	$n$ 限制	评测程序	依赖组	说明
0		--	非自适应	--	样例
1	14	$n \le 63$	自适应	0
2	8	--		--	图为 special$^1$
3	11				图为 special$^2$
4	12				图为 special$^3$
5	9	$n \le 100$		0,1
6	10	$n \le 400$	非自适应	0
7	9		自适应	0,1,5,6
8		$n \le 450$	非自适应	0,6
9	10	--		0,6,8
10	9		自适应	0--9	原题为赛后反馈组

特殊图定义

special$^1$：存在一个顶点排列 $v_1,v_2,\ldots,v_n$，使得对任意 $i<j$，边方向均为 $v_i \to v_j$。

special$^2$：对任意编号 $v>2$ 的顶点，它到顶点 $1$ 或顶点 $2$ 的边中，至少有一条是从 $v$ 指向该顶点；也可以两条都从 $v$ 指向 $1,2$。

special$^3$：满足 $n\ge 4$，并且存在一个顶点排列 $v_1,v_2,\ldots,v_n$，使得边 $(v_i,v_{i+1})$ 的方向为 $v_i \to v_{i+1}$，而任意其他边 $(v_i,v_j)$（$i+1<j$）的方向为 $v_j \to v_i$。

提交说明

在 Hydro 上提交时，仍然提交普通交互式程序。你的程序应该：

1. 从标准输入读取 $g,t,n$ 以及交互返回；
2. 向标准输出输出 ? u v 或 ! u；
3. 每次输出后刷新输出流。

不要尝试读取隐藏图矩阵。隐藏图只由官方 interactor.cpp 掌握。