这是一个交互问题。
给定一个简单的无向图,其中 $$$n$$$ 顶点编号从 $$$1$$$ 到 $$$n$$$,您的任务是为所有顶点着色,使得对于每种颜色 $$$c$$$,满足以下条件:
1. 颜色为$$$c$$$的顶点集是相连的;
2. $$$s_c \leq n_c^2$$$,其中$$$n_c$$$是颜色为$$$c$$$的顶点数量,$$$s_c$$$是颜色为$$$c$$$的顶点的度数总和。
最初,您仅获得顶点数 $$$n$$$ 以及每个顶点的度数。
在每个查询中,您可以选择一个顶点$$$u$$$。作为响应,如果这是顶点 $$$u$$$ 上的第 $$$k$$$ 查询,您将获得与 $$$u$$$ 相关的第 $$$k$$$ 条边。
您最多可以进行 $$$n$$$ 查询。
如果无向图不包含多条边或自环,那么它就是简单的。
顶点的度数是与其相关的边的数量。
如果对于 S$$$ 中的每两个不同的顶点 $$$u, v,有一条仅通过 $$$S$$$ 中的顶点,连接 $$$u$$$ 和 $$$v$$$ 的路径,则一组顶点 $$$S$$$ 是连通的。也就是说,存在一系列边 $$$(u_1, v_1), (u_2, v_2), \dots, (u_k, v_k)$$$ 和 $$$k \geq 1$$$ 使得
1. 对于每个 $$$1 \leq i < k$$$,$$$u_1 = u$$$、$$$v_k = v$$$ 和 $$$v_i = u_{i+1}$$$;和
2. 对于每个 $$$1 \leq i \leq k$$$,$$$u_k \in S$$$ 和 $$$v_k \in S$$$。
互动
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。以下行包含每个测试用例的描述和交互部分。
对于每个测试用例,您可以通过读取第一行中的整数 $$$n$$$ ($$$1\le n \le 1000$$$) 来开始交互,该整数表示图中的顶点数。
第二行包含 $$$n$$$ 整数 $$$d_1, d_2, \dots, d_n$$$ ($$$0 \leq d_i \leq n - 1$$$),其中 $$$d_i$$$ 是顶点 $$$i$$$ 的度数。
要对顶点 $$$u$$$ ($$$1 \leq u \leq n$$$) 进行查询,您应该输出
- “?$$$u$$$”
要给出答案,您应该输出
- “!$$$c_1$$$ $$$c_2$$$ $$$\点$$$ $$$c_n$$$"
保证该图是一个简单的无向图。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
如果您的查询格式无效,或者您输入了超过$$$n$$$“?”查询,您将收到错误答案判决。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客格式
hack的第一行包含一个整数$$$t$$$ ($$$1 \leq t \leq 1000$$$),表示测试用例的数量。以下行包含每个测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 1000$$$),表示图中的顶点数。
然后是 $$$n$$$ 行。第 $$$i$$$ 行包含一个整数 $$$d_i$$$ ($$$0 \leq d_i \leq n - 1$$$),表示顶点 $$$i$$$ 的度数,然后是 $$$d_i$$$ 不同的整数 $$$e_{i,1}, e_{i,2}, \dots, e_{i,d_i}$$$ ($$$1 \leq e_{i, j} \leq n$$$ 和 $$$e_{i,j} \neq i$$$),其中 $$$\left(i, e_{i,j}\right)$$$ 是与顶点 $$$i$$$ 相关的第 $$$j$$$ 条边。
应该保证该图是一个简单的无向图。
应保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
示例
输入 #1
1 5 2 2 2 2 0 2 4 2 4
输出 #1
? 1 ? 1 ? 3 ? 3 ! 1 1 2 2 3
注意
在该示例中,只有一个测试用例。
在测试用例中,有 $$$n = 5$$$ 个顶点,其中度数为 $$$2$$$ 的顶点为 $$$1, 2, 3, 4$$$,度数为 $$$0$$$ 的顶点为 $$$5$$$。很明显,顶点 $$$5$$$ 是孤立的,即它不连接到任何其他顶点。
示例输入和输出中显示了可能的交互,其中 $$$4$$$ “?”对顶点 $$$1$$$ 进行两次查询,对顶点 $$$3$$$ 进行两次查询。根据对这些查询的响应,我们知道每个顶点 $$$1$$$ 和顶点 $$$3$$$ 连接到两个顶点 $$$2$$$ 和 $$$4$$$。
示例输出中显示了一个可能的解决方案,其中顶点 $$$1$$$ 和顶点 $$$2$$$ 由 $$$1$$$ 着色,顶点 $$$3$$$ 和顶点 $$$4$$$ 由 $$$2$$$ 着色,顶点 $$$5$$$ 由 $$$3$$$ 着色。可以看出,该解满足如下所需条件。
- 对于颜色 $$$c = 1$$$,顶点 $$$1$$$ 和顶点 $$$2$$$ 连接。此外,$$$n_1 = 2$$$ 和 $$$s_1 = d_1 + d_2 = 2 + 2 = 4 \leq n_1^2 = 2^2 = 4$$$;
- 对于颜色 $$$c = 2$$$,顶点 $$$3$$$ 和顶点 $$$4$$$ 已连接。此外,$$$n_2 = 2$$$ 和 $$$s_2 = d_3 + d_4 = 2 + 2 = 4 \leq n_2^2 = 2^2 = 4$$$;
- 对于颜色 $$$c = 3$$$,只有一个顶点(顶点 $$$5$$$)由 $$$3$$$ 着色。此外,$$$n_3 = 1$$$ 和 $$$s_3 = d_5 = 0 \leq n_3^2 = 1^2 = 1$$$。