{"problem":{"name":"[CoE R4 C] 网格","description":{"content":"**这是一道交互题。** 有一张 $n$ 个点的无向无权图。 这张图有一个特殊性质：存在一个点 $u \\ (1 \\leq u \\leq n)$ 到正整数对 $(x, y) \\ (1 \\leq x \\leq l, 1 \\leq y \\leq c)$ 的**一一对应**关系，使得 $n = l \\cdot c$，且点 $u, v$ 间存在边当且仅当 $u, v$ 对应的数对 $(x_u, y_u)","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8303"},"statements":[{"statement_type":"Markdown","content":"**这是一道交互题。**\n\n有一张 $n$ 个点的无向无权图。\n\n这张图有一个特殊性质：存在一个点 $u \\ (1 \\leq u \\leq n)$ 到正整数对 $(x, y) \\ (1 \\leq x \\leq l, 1 \\leq y \\leq c)$ 的**一一对应**关系，使得 $n = l \\cdot c$，且点 $u, v$ 间存在边当且仅当 $u, v$ 对应的数对 $(x_u, y_u), (x_v, y_v)$ 满足 $|x_u - x_v| + |y_u - y_v| = 1$。换而言之，这张图和 $l$ 行 $c$ 列的网格图同构。\n\n现在，你要通过一些询问还原这张图的结构。每次询问时，你需要给定一个点 $u \\ (1 \\leq u \\leq n)$。询问的返回值是一个长为 $n$ 的数组 $\\{d_i\\} \\ (1 \\leq i \\leq n)$，表示点 $u, i$ 间的最短路径所经过的边数。\n\n请你使用不超过 $q$ 次询问，还原出这张图的结构。\n\n---\n\n### 交互格式\n\n**本题有多组数据。**\n\n首先输入一个整数 $T$，表示数据组数。\n\n对于每组数据：\n\n- 首先输入一个整数 $n$，表示图的点数。\n- 接下来，你可以执行一些询问。对于每次询问，输出一个整数 $u$，为你询问的点。然后，输入 $n$ 个整数 $\\{d_i\\}$，为询问的返回值。\n- 当你确定答案后，输出一个整数 $0$，然后输出答案。\n\n在输出答案时：\n\n- 第一行输出两个整数 $l, c$；\n- 接下来，输出 $l$ 行 $c$ 列整数，为你还原的对应关系。第 $i$ 行 $j$ 列的数为 $(i, j)$ 对应的编号。\n\n如果有多个答案，你可以输出任意一个。一个答案是正确的，当且仅当它和标准答案无法被任何询问区分：也就是，在这两个答案对应的网格图中，任意点对间的最短路径所经过的边数都是相同的。\n\n---\n\n请注意：**在每次执行询问或者输出答案后，你应该清空缓冲区：**\n\n- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。\n- 在 Java 中，使用 `System.out.flush()`。\n- 在 Python 中，使用 `stdout.flush()`。\n- 在 Pascal 中，使用 `flush(output)`。\n- 对于其他语言，请自行查阅对应语言的帮助文档。\n\n## Input\n\n见「交互格式」。\n\n## Output\n\n见「交互格式」。\n\n[samples]\n\n## Note\n\n### 样例 $1$ 解释\n\n对于样例，以下 $3$ 行 $2$ 列的网格图也是正确的输出。\n\n```\n3 2\n4 2\n3 5\n6 1\n```\n\n左边是样例对应的网格图，右边是以上输出对应的网格图。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/jy23v0au.png)\n\n---\n\n### 评分标准\n\n对于一个子任务，令 $q_{\\max}$ 为你在这个子任务的所有测试数据中的最大询问次数。\n\n如果交互的格式不合法，运行超出了时间限制，或者你的答案不正确，或者 $q_{\\max} > q$，你的得分为 $0$。\n\n否则，对于子任务 $1 \\sim 3$，你得满分；对于子任务 $4$，你的分数由下表给出：\n\n| 条件 | 分数 |\n| :-: | :-: |\n| $q_{\\max} \\leq 3$ | $61$ |\n| $q_{\\max} = 4$ | $41$ |\n| $q_{\\max} = 5$ | $31$ |\n| $q_{\\max} = 6$ | $21$ |\n| $q_{\\max} \\geq 7$ | $11$ |\n\n---\n\n### 数据规模\n\n**本题采用捆绑测试。**\n\n| 子任务 | 分值 | $n \\leq$ | $q = $  | 特殊性质 |\n| :-: | :-: | :-: | :-: | :-: |\n| $1$ | $3$ | $4$ | $4$ | 无 |\n| $2$ | $13$ | $10^5$ | $4$ | 存在解使得 $l = 1$ |\n| $3$ | $23$ | $36$ | $36$ | 存在解使得 $2 \\leq l, c \\leq 6$ |\n| $4$ | $61$ | $10^5$ | $12$ | 无 |\n\n对于所有数据，保证 $1 \\leq T \\leq 10^3$，$1 \\leq n \\leq 10^5$，$\\sum n \\leq 3 \\times 10^5$。\n\n在部分测试数据中，交互器是自适应的。也就是，图的结构可能会根据你的询问而变化。但是可以保证：在每次询问之后，存在至少一个答案符合当前所有询问的返回值。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8303","tags":["洛谷原创","交互题","Special Judge","O2优化","洛谷月赛"],"sample_group":[["1\n6\n\n0 2 2 3 1 1\n\n2 0 2 1 1 3\n\n2 2 0 1 1 1\n\n3 1 1 0 2 2\n\n1 1 1 2 0 2\n\n1 3 1 2 2 0","\n\n1\n\n2\n\n3\n\n4\n\n5\n\n6\n\n0\n2 3\n2 5 1\n4 3 6"],["2\n1\n\n\n\n2\n\n1 0","\n\n0\n1 1\n1\n\n2\n\n0\n2 1\n1\n2"]],"created_at":"2026-03-03 11:09:25"}}