题目详情题解（0）讨论（0）提交记录（0）

CFCF2196C2.Interactive Graph (Hard Version)

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

这是该问题的难度较高的版本。不同之处在于，在本版本中，你最多只能询问 n+mn+m 个问题，并且 n≤30n \leq 30。只有在你解决了该问题的所有版本后，才可以对其进行 Hack。

这是一个交互式问题。

命题人想出了一个没有环和重边的有向无环图（DAG），该图有 nn 个点和 mm 条边。

你的任务是确定图中具体有哪些边。为此，你可以提出形式为：“图中所有路径按字典序排序后的第 kk 条路径长什么样？”的问题。

图中的一条路径指的是一组顶点序列 u1,u2,…,ulu_{1}, u_{2}, \dots, u_{l}，使得对于任意 i<li < l，图中存在一条有向边 (ui,ui+1)(u_{i}, u_{i+1})。

你需要通过不超过 n+mn+m 次的提问来完成任务。

∗^{\ast} 序列 aa 在字典序上小于序列 bb 当且仅当满足下列之一：

  • aa 是 bb 的前缀，且 a≠ba \ne b；
  • 在 aa 和 bb 的第一个不同位置，aa 的对应元素小于 bb 的对应元素。

输入格式

每个测试包含多组数据。第一行包含一个整数 tt（1≤t≤101 \le t \le 10），表示测试用例的数量。每个测试用例包含一行，包含一个整数 nn（1≤n≤301 \le n \le 30），表示图中的顶点数。

保证所给的图中不包含环和重边。

注意，你并不知道 mm 的值！

输入输出样例

  • 输入#1

    3
5

1 1

2 1 2

3 1 2 4

3 1 2 5

2 1 3

3 1 3 4

3 1 3 5

1 2

1 3

1 4

1 5

1

0

2

1 1

1 2

2 2 1

    输出#1

    ? 1

? 2

? 3

? 4

? 5

? 6

? 7

? 8

? 11

? 14

? 15

! 6
1 3
1 2
2 4
3 4
2 5
3 5

? 2

! 0

? 1

? 2

? 3

! 1
2 1

说明/提示

第一个测试用例对应的图如下。

在该图中，共有 1515 条路径，按字典序排序如下：

  • 11
  • 1→21 \to 2
  • 1→2→41 \to 2 \to 4
  • 1→2→51 \to 2 \to 5
  • 1→31 \to 3
  • 1→3→41 \to 3 \to 4
  • 1→3→51 \to 3 \to 5
  • 22
  • 2→42 \to 4
  • 2→52 \to 5
  • 33
  • 3→43 \to 4
  • 3→53 \to 5
  • 44
  • 55
首页