这是一道交互题。

跳蚤们已经修好了$m$条道路连通了$n(n\ge 2)$只Dog（这些道路中无重边无自环）。但是它们马上发现了一个很大的问题，$n$只Dog中并不全是SingleDog，也有一些是DoubleDog。

Dog们给了跳蚤们一个提示：这$m$条道路中，每一条都连接的是一只SingleDog和一只DoubleDog。不存在一条道路连接两只SingleDog或者两只DoubleDog。即图是一张二分图。

现在跳蚤们需要你把这些Dog给划分出来。跳蚤们不直接告诉你这$m$条道路，而是给了你这样一个功能：你可以进行若干次询问。每次询问你告诉跳蚤们一些点对，这些点对对应一个道路的集合，跳蚤们将回答如果将$m$条道路中在这个集合的道路去掉之后这$n$只Dog是否仍然连通。注意道路 $(x,y)$ 和 $(y,x)$ 是等价的，一次询问中一条道路加入多次和加入一次的效果相同。

你需要在2000次询问内内找出所有的SingleDog或者DoubleDog（即输出二分图的一侧），或判断跳蚤们的提示是错误的（图不是二分图），在这个情况下返回空集。可以证明因为图连通且点数至少为2，二分图的一部分不可能是空集。

任务

你需要实现下面的过程：

std::vector<int> check_bipartite(int vsize);

其中 vsize 是Dog的数量，也就是题目描述中的 $n$。

你可以调用以下过程和交互库进行交互：

bool query(std::vector<std::pair<int, int>> banned_edges);

其中 banned_edges 是一个包含点对的 vector，表示你要去掉的点对。当图仍然联通时返回值为true，否则为false。你必须保证所有点对合法，否则你将得到 0 分。所谓点对合法就是值点对中的每个编号都必须合法，且两个点不能相同。

评测方式

评测程序示例将读入如下格式的输入数据：

第一行包括两个正整数 $n$ 和 $m$；

接下来 $m$ 行，每行表示一条边的两个端点。

请注意点的编号从0开始。

评测程序示例将输出如下格式的输出数据：

第一行一个非负整数，表示二分图一部分的点数，如果是0表示不是二分图。

接下来一行空格隔开的数表示二分图一侧的每个点。

请注意点的编号从0开始。

样例一至样例四

见样例及交互库下载

限制与约定

对于所有数据，保证 $n-1\le m\le \frac{n(n-1)}{2}$，且 $2\le n\le 200$。

Subtask 1 (13 分): $n\le 10$，保证图是二分图。

Subtask 2 (24 分): $n\le 40$，保证图是二分图。

Subtask 3 (30 分): $n\le 100$

Subtask 4 (33 分): $n\le 200$

交互式类型的题目怎么本地测试

在本题中，本地测试时可以将 graderlib.cpp 和 grader.cpp 一起粘到提交程序之前。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例及交互库下载