CF1033E.Hidden Bipartite Graph

Bob has a simple undirected connected graph (without self-loops and multiple edges). He wants to learn whether his graph is bipartite (that is, you can paint all vertices of the graph into two colors so that there is no edge connecting two vertices of the same color) or not. As he is not very good at programming, he asked Alice for help. He does not want to disclose his graph to Alice, but he agreed that Alice can ask him some questions about the graph.

The only question that Alice can ask is the following: she sends $s$ — a subset of vertices of the original graph. Bob answers with the number of edges that have both endpoints in $s$. Since he doesn't want Alice to learn too much about the graph, he allows her to ask no more than $20000$ questions. Furthermore, he suspects that Alice might introduce false messages to their communication channel, so when Alice finally tells him whether the graph is bipartite or not, she also needs to provide a proof — either the partitions themselves or a cycle of odd length.

Your task is to help Alice to construct the queries, find whether the graph is bipartite.

Bob 有一张简单的无向连通图（不含自环和重边）。他想判断这张图是否为二分图（即能否将图的所有顶点染成两种颜色，使得任意一条边的两个端点颜色不同）。由于 Bob 编程水平有限，他向 Alice 寻求帮助。但他不愿将自己的图直接透露给 Alice，仅同意 Alice 可以向他提出若干关于该图的问题。

Alice 唯一被允许提出的问题形式如下：她发送一个顶点子集 $s$（$s$ 是原图顶点集的子集），Bob 则返回满足“两个端点均属于 $s$”的边的数量。由于 Bob 不希望 Alice 过多地获知图的信息，他限制 Alice 最多只能提出 $20000$ 个问题。此外，Bob 怀疑通信信道中可能存在 Alice 故意引入的虚假消息，因此当 Alice 最终告知 Bob 该图是否为二分图时，她还需提供一份证明——要么给出该图的一个二分图划分（即两个顶点集合），要么给出一个长度为奇数的环。

你的任务是帮助 Alice 设计查询方案，并判断该图是否为二分图。

The first line contains a single integer $n$ ($1 \leq n \leq 600$) — the number of vertices in Bob's graph.

第一行包含一个整数 $n$（$1 \leq n \leq 600$）—— 表示 Bob 图中的顶点数。

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.

在第一种情况下，Alice 得知整个图中有 $4$ 条边。在接下来的三次查询中，她得知顶点 $1$ 有两个邻接点：$3$ 和 $4$；随后她又得知顶点 $2$ 与 $4$ 相邻，但顶点 $3$ 与 $4$ 不相邻。剩余的一条边只有一种可能，即 $(2, 3)$。这意味着该图是一个包含四个顶点的环，其中 $(1, 2)$ 构成一个划分，$(3, 4)$ 构成另一个划分。此时，在第二行输出 “3 4” 也是合法的。

在第二种情况下，我们同样有一个含四个顶点、四条边的图。在第二次查询中，Alice 得知顶点集 $(1, 2, 4)$ 之间共有三条边。这种情况唯一可能的构型是这三个顶点构成一个三角形。由于三角形不是二分图，Alice 可将其作为非二分性的证明提交。注意，她并未获知第四条边的位置，但仍然能够正确回答 Bob 的问题。