← 返回题目列表

Codeforces · 1033/E

E. 隐藏二分图

中文机器翻译题面 查看原题

Bob 有一个简单的无向连通图(没有自环和多条边)。他想知道他的图是否是二分图(也就是说,你可以将图的所有顶点绘制成两种颜色,这样就没有边连接相同颜色的两个顶点)。由于他不太擅长编程,他向Alice寻求帮助。他不想向 Alice 透露他的图表,但他同意 Alice 可以问他一些有关图表的问题。

Alice 可以问的唯一问题如下:她发送 $$$s$$$ — 原始图的顶点子集。 Bob 回答了两个端点都在 $$$s$$$ 中的边的数量。由于他不希望 Alice 了解太多有关图表的信息,因此他允许她提出不超过 $$$20000$$$ 的问题。此外,他怀疑爱丽丝可能会向他们的通信渠道引入虚假消息,因此当爱丽丝最终告诉他该图是否是二分图时,她还需要提供一个证明——要么是分区本身,要么是奇数长度的循环。

你的任务是帮助 Alice 构建查询,确定图是否是二分图。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 600$$$) — Bob 图中的顶点数。

互动

首先,读取一个整数 $$$n$$$ ($$$1\leq n\leq 600$$$) — Bob 图中的顶点数。

要进行查询,请打印两行。第一个的格式应为“? k” ($$$1 \leq k \leq n$$$),其中 $$$k$$$ 是要查询的集合的大小。第二行应包含 $$$k$$$ 空格分隔的不同整数 $$$s_1, s_2, \dots, s_k$$$ ($$$1 \leq s_i \leq n$$$) - 查询集的顶点。

每次查询后读取单个整数 $$$m$$$ ($$$0 \leq m \leq \frac{n(n-1)}{2}$$$) - 集合 $$$\{s_i\}$$$ 的顶点之间的边数。

您提出的查询不得超过 $$$20000$$$。

如果 $$$m = -1$$$,则意味着您提出的查询数量超出了允许的数量,或者提出了无效查询。您的程序应立即终止(例如,通过调用 exit(0))。您将收到错误答案;这意味着您提出的查询超出了允许的范围,或者提出了无效的查询。如果您忽略这一点,您可以获得其他结论,因为您的程序将继续从关闭的流中读取。

打印查询后,不要忘记打印行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

当你知道答案时,你需要打印它。

答案的格式取决于图是否是二分图。

如果该图是二分图,则打印两行。第一个应包含字母“Y”(“YES”的缩写),后跟一个空格,然后是单个整数 $$$s$$$ ($$$0 \leq s \leq n$$$) - 其中一个分区中的顶点数。第二行应包含 $$$s$$$ 整数 $$$a_1, a_2, \dots, a_s$$$ - 属于第一个分区的顶点。所有 $$$a_i$$$ 必须是不同的,并且主图中的所有边必须在集合 $$$\{a_i\}$$$ 中恰好有一个端点。

如果该图不是二分图,则打印两行。第一个应该包含字母“N”(“NO”的缩写),后跟一个空格,然后是一个整数 $$$l$$$($$$3 \leq l \leq n$$$) - 一个奇数长度的简单循环的长度。第二行应包含 $$$l$$$ 整数 $$$c_1, c_2, \dots, c_l$$$ - 沿循环的顶点。它必须认为对于所有 $$$1 \leq i \leq l$$$,主图中都有一条边 $$$\{c_i, c_{(i \mod l)+1}\}$$$,并且所有 $$$c_i$$$ 都是不同的。

如果有多个可能的答案,您可以打印其中任何一个。

Hacks 格式 对于 hacks,请使用以下格式:

第一行包含两个整数 $$$n$$$ 和 $$$m~(1 \leq n \leq 600, 0 \leq m \leq \frac{n(n-1)}{2})$$$ - 分别是图的顶点数和边数。

接下来的 $$$m$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i~(1 \leq u_i, v_i \leq n)$$$ 表示 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条边。不能有任何重边,不能有环,并且图必须是连通的。

例如,您需要使用此测试来获取第一个样本:

示例

输入 #1

4
4
0
1
1
1
0

输出 #1

? 4
1 2 3 4
? 2
1 2
? 2
1 3
? 2
1 4
? 2
2 4
? 2
3 4
Y 2
1 2

输入 #2

4
4
3

输出 #2

? 4
1 4 2 3
? 3
1 2 4
N 3
2 1 4

注意

在第一种情况下,Alice 得知整个图中有 $$$4$$$ 边。在接下来的三个查询过程中,她了解到顶点 $$$1$$$ 有两个邻居:$$$3$$$ 和 $$$4$$$。然后她了解到,虽然顶点 $$$2$$$ 与 $$$4$$$ 相邻,但顶点 $$$3$$$ 与 $$$4$$$ 不相邻。剩下的边只有一个选项,那就是$$$(2, 3)$$$。这意味着该图是四个顶点上的循环,其中 $$$(1, 2)$$$ 是一个分区,$$$(3, 4)$$$ 是第二个分区。这里,在第二行输出“3 4”也是有效的。

在第二种情况下,我们还有一个有四个顶点和四个边的图。在第二个查询中,Alice 了解到顶点 $$$(1, 2, 4)$$$ 之间存在 3 条边。发生这种情况的唯一方法是它们形成三角形。由于三角形不是二分的,Alice 可以将其报告为证明。请注意,她不知道第四条边在哪里,但她无论如何都能正确回答鲍勃。