7 人解决，20 人已尝试。
9 份提交通过，共有 114 份提交。
8.1 EMB 奖励。
单点时限: 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$ 个互不相同的整数，表示图的左半部分。你可以以任意顺序输出。如果有多解输出任意一解。
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
Case #1: 2 3 Case #2: NO Case #3: 1 2 3 6
7 人解决，20 人已尝试。
9 份提交通过，共有 114 份提交。
8.1 EMB 奖励。