3647. 小猪分类

单测试点时限: 5.0 秒

内存限制: 512 MB

你女朋友最近叕不理你了。这一定是因为你双十一买的礼物太廉价了。异地恋实在是太辛苦了,浦西到浦东的距离,对于你来说,就像是上海到北京的距离。

曾有诗这样写道:

世上最遥远的距离,不是生与死的距离,不是天各一方,而是我就站在你面前,你却不知道我爱你。

所以你决定买一些小猪猪送给她,但是遗憾的是有些小猪猪在一起会打架,因此你不得不从中间挑出恰好 只送给她,而你自己留下 只。

简而言之就是需要将一个无向图划成点数为 的两部分,使得左半部分内部和右半部分内部都没有边。

输入

第一行一个正整数 表示数据组数。

接下来每组数据,第一行有三个整数 , , 满足 , , ,分别表示无向图的点数、边数和左半部分的点数。 没有在输入中给出。

然后是 行表示边的信息。每一行是两个整数 ()。输入保证同一对 至多出现一次。

输入保证 组数据的 之和不超过 之和不超过

输出

对于每组数据首先输出 Case #x:,其中 x 是从 1 开始的测试数据编号。

如果该组数据无解,输出 NO。否则输出 个互不相同的整数,表示图的左半部分。你可以以任意顺序输出。如果有多解输出任意一解。

样例

Input
3
3 2 2
1 2
1 3
4 2 1
1 4
2 3
6 4 4
1 5
5 6
4 2
4 3
Output
Case #1: 2 3
Case #2: NO
Case #3: 1 2 3 6

5 人解决,14 已尝试。

7 份提交通过,共有 63 份提交。

9.4 EMB 奖励。

创建: 1 月,2 周前.

修改: 4 周,1 天前.

最后提交: 4 周前.

来源: EOJ Monthly 2018.11

标签