题目描述

题目译自 PA 2015 Runda 2 Mistrzostwa

世界计算机运动锦标赛是每个电子娱乐爱好者日历上最重要的活动。今年，锦标赛的组织工作落到了拜托西亚王国的肩上。国王 Bajtazar 任命的组织委员会面临一项艰巨任务——他们必须决定在拜托西亚的哪些城市举办比赛。拜托西亚有 $n$ 座城市（编号从 $1$ 到 $n$），通过 $m$ 条双向道路连接。

委员会预计，来自世界各地的粉丝将蜂拥而至参加锦标赛。众所周知，粉丝们会频繁地在举办城市之间旅行，以观看不同项目的比赛。因此，优先考虑的是，确保举办比赛的城市集合具有良好的连通性。

如果满足以下条件，我们称城市集合 $S$ 为良好连通的：

1. 集合 $S$ 中的每座城市至少有 $d$ 条直接道路连接到集合 $S$ 中的其他城市。
2. 集合 $S$ 中的任意两座城市之间存在一条仅通过集合 $S$ 内城市的路径。

此外，为了尽量减少每座城市平均接待的游客数量，委员会希望选出的城市集合尽可能大。

输入格式

输入数据的第一行包含三个整数 $n, m, d$ $(2 \leq n \leq 200000, 1 \leq m \leq 200000, 1 \leq d < n)$，分别表示拜托西亚的城市数量、道路数量和参数 $d$。

接下来的 $m$ 行描述拜托西亚的道路：第 $i$ 行包含两个整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i})$，表示第 $i$ 条道路连接编号为 $a_{i}$ 和 $b_{i}$ 的城市。每对城市之间最多只有一条直接道路。

输出格式

如果无法选择一个良好连通的拜托西亚城市集合，则输出 NIE。

否则，输出一个最大的良好连通城市集合，格式如下：第一行包含一个数字 $k$，表示找到的集合大小。第二行包含 $k$ 个数字，按升序排列，表示集合中城市的编号。

如果存在多个解，你的程序可以输出其中任意一个。

4 4 2
1 2
2 3
3 4
4 2

3
2 3 4

3 2 2
1 2
2 3

NIE