EOJ Monthly 2018.11

E. 小猪分类

单点时限: 5.0 sec

内存限制: 512 MB

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

曾有诗这样写道:

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

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

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

输入格式

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

接下来每组数据,第一行有三个整数 $n$, $m$, $k_1$ 满足 $2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$, $1 \le k_1 \le n - 1$,分别表示无向图的点数、边数和左半部分的点数。$k_2 = n - k_1$ 没有在输入中给出。

然后是 $m$ 行表示边的信息。每一行是两个整数 $u_i$ 和 $v_i$ ($1 \le u_i,v_i \le n, u_i \ne v_i$)。输入保证同一对 $(u_i, v_i)$ 至多出现一次。

输入保证 $T$ 组数据的 $n$ 之和不超过 $6 \cdot 10^5$,$m$ 之和不超过 $6 \cdot 10^5$。

输出格式

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

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

样例

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