CF1033E Hidden Bipartite Graph

**这是一道交互题。** 给定一个连通图（不包括自环和重边），你可以询问一个点集 $s$，系统会返回在 $s$ 中有两个端点的边的数量。你最多可以询问 $20000$ 次。 你需要判断这个图是不是一个二分图。

输入一个数 $n$ ( $1\le n\le 600$ )，表示连通图的点数。

首先，读入一个数 $n$，表示连通图的点数。 对于询问，输出两行。第一行输出 “? k” ( $1\le k\le n$ )，$k$ 表示点集的大小。第二行输出 $k$ 个不同的整数 $s_1,s_2,\dots,s_k$ ( $1\le s_i \le n$ )，表示点集。 每次询问后会读入一个数字 $m$ ( $0\le m\le \frac{n(n-1)}{2}$ )，表示在点集 $\{s\}$ 中有两个端点的边的数量。 你最多可以询问 $20000$ 次。 如果 $m=-1$，说明你询问的次数过多，或者询问是无效的。这时，程序应当立刻终止（比如说直接 `exit(0)`）。如果这样做，评测将会返回 `Wrong Answer`，否则将会返回其他结果。 当你知道答案后，你需要输出结果。输出的形式取决于这个图是不是二分图。 如果是，输出两行。第一行输出一个字符 `Y` 和一个数字 $s$ ( $0\le s\le n$ )，$s$ 表示二分图左部/右部的大小。第二行则输出 $s$ 个不同整数 $a_1,a_2,\dots,a_s$ ( $1\le a_i\le n$ )，表示二分图的左部/右部。 如果不是，输出两行。第一行输出一个字符 `N` 和一个奇数 $s$ ( $3\le s \le n$ )。第二行则输出 $s$ 个不同整数 $a_0,a_1,\dots,a_{s-1}$ ( $1\le a_i\le n$ ) ，必须保证对于任意 $i$，$a_i$ 与 $a_{(i+1)\bmod s}$ 之间有一条边。 如果有多种答案，你只需要输出其中一种。

In the first case, Alice learns that there are $ 4 $ edges in the whole graph. Over the course of the next three queries, she learns that vertex $ 1 $ has two neighbors: $ 3 $ and $ 4 $ . She then learns that while vertex $ 2 $ is adjacent to $ 4 $ , the vertex $ 3 $ isn't adjacent to $ 4 $ . There is only one option for the remaining edge, and that is $ (2, 3) $ . This means that the graph is a cycle on four vertices, with $ (1, 2) $ being one partition and $ (3, 4) $ being the second. Here, it would be also valid to output "3 4" on the second line. In the second case, we also have a graph on four vertices and four edges. In the second query, Alice learns that there are three edges among vertices $ (1, 2, 4) $ . The only way this could possibly happen is that those form a triangle. As the triangle is not bipartite, Alice can report it as a proof. Notice that she does not learn where the fourth edge is, but she is able to answer Bob correctly anyway.