题目描述

考虑一个包含 $n$ 个节点的有向图，节点编号为 $1,2,\dots,n$。如果对于每一对不同的节点，两个方向中恰好存在一条有向边，则称该图为一张竞赛图。也就是说，对于任意两个不同节点 $u$ 和 $v$，要么存在从 $u$ 到 $v$ 的边，要么存在从 $v$ 到 $u$ 的边。

一条哈密顿回路是一个序列 $c_1, c_2, \dots, c_n$，它沿着图中的边访问所有节点并最终回到起点。对于所有 $1 \le i \le n-1$，必须存在从 $c_i$ 到 $c_{i+1}$ 的边；此外，还必须存在从 $c_n$ 到 $c_1$ 的边。

你可以自由构造一张 $n$ 个节点的竞赛图。随后，节点的编号会被随机打乱。通过针对打乱后图中的边的方向进行询问，你能否找到一条哈密顿回路？

交互方式

本题为交互题。首先读入两个整数 $n$ 和 $t$：分别表示节点数与测试数据组数。

接下来，输出 $n$ 行来描述竞赛图。在第 $u$ 行中输出 $n$ 个字符 "0" 或 "1"。位置 $v$ 上的字符 "1" 表示存在一条从 $u$ 到 $v$ 的边。从节点到自身的边不应存在。

随后会进行 $t$ 组测试。每组测试均使用你提供的同一张图，但节点编号会被打乱并对你的程序保密。你可以进行若干次询问，之后需要给出一个哈密顿回路。

若要发起询问，请输出 "? $u$ $v$"，其中 $1 \le u,v \le n$ 是打乱后的图中的两个不同节点。交互库会回复 ">" 表示存在从 $u$ 到 $v$ 的边，或 "<" 表示存在从 $v$ 到 $u$ 的边。

当你找到一条哈密顿回路后，请输出 "!"，后跟 $n$ 个整数 $c_1, c_2, \dots, c_n$。注意这些整数 $c_i$ 应遵循打乱后的节点编号。在你输出答案后，下一组测试将立即开始。

你可以在此处下载测试脚本。脚本的开头包含了使用说明。

5 2





>

>

>

>

>


<

>

>

<

>

01110
00101
00010
01001
10100
? 1 2

? 2 3

? 3 4

? 4 5

? 5 1

! 1 2 3 4 5
? 1 2

? 1 5

? 4 3

? 4 5

? 3 2

! 1 5 4 3 2

提示

解释

在第一组测试数据中，打乱后的编号恰好与原编号一致，因此 $1,2,3,4,5$ 就是一条哈密顿回路。

在第二组测试数据中，节点编号 $1,2,3,4,5$ 依次被随机打乱为 $2,4,1,5,3$。序列 $1,5,4,3,2$ 确实是一条哈密顿回路，因为它在原图中对应于 $3,4,2,5,1$。

下图中，左图为原图，右图为第二组测试数据中打乱后的图。两条哈密顿回路以红色高亮标注。

:::align{center} :::

数据范围

• $4 \le n \le 500$
• $1 \le t \le 200$

评分

每个子任务中仅有一个测试输入，包含 $t = 200$ 组测试数据。在每组测试数据中，图的节点编号会被均匀随机地打乱。在单组测试数据中发起超过 $10^4$ 次询问将导致判决为 WRONG ANSWER。

设 $Q$ 为你的程序在某一子任务所有测试数据中询问次数的平均值。若 $Q$ 不超过指定限制，你将获得该子任务的分数。

子任务	约束条件	分值
1	$n = 4, Q \le 12$	$5$
2	$n = 50, Q \le 1225$	$7$
3	$n = 50, Q \le 300$	$12$
4	$n = 500, Q \le 1500$	$1\sim 76$

在子任务 4 中，你的得分根据以下公式计算：

$$\left\lfloor \frac {25\,000} {\max(750, Q) - 500} - 24 \right\rfloor$$

例如，如果你的程序平均询问次数为 $Q=1500$，你将从此子任务获得 1 分；若 $Q=1000$，获得 26 分；若 $Q=750$，获得 76 分。

翻译由 DeepSeek V4 Pro 完成