题目背景

译自 PA 2015 R2.

题目描述

给定一张 $n$ 个点 $m$ 条边的简单（无重边自环的）无向图 $G=(V,E)$。其中节点编号 $1\sim n$。

给定正整数 $d$。选出一个最大的点集 $S\subseteq V$，满足：

• $\forall u\in S$，$\displaystyle \sum_{v\in S} [(u,v)\in E]\ge d$。换句话说，$u$ 向 $S$ 内点至少连了 $d$ 条边。
• $S$ 的导出子图（induced subgraph）是连通的。

你需要构造一个 $S$ 使得 $|S|$ 取到最大值，或者报告无解。

点集 $V'\subseteq V$ 的导出子图定义为 $G'=(V',E')$，其中 $E'=\{(u,v)\in E: u\in V'\land v\in V'\}$。

输入格式

第一行，三个正整数 $n,m,d$。

接下来 $m$ 行，每行两个正整数 $u,v$，表示 $(u,v)\in E$。

输出格式

如果符合条件的 $S$ 不存在，输出一行一个 $\texttt{NIE}$。

否则，第一行输出 $|S|$，第二行升序输出 $S$ 中节点的编号。

4 4 2
1 2
2 3
3 4
4 2

3
2 3 4

3 2 2
1 2
2 3

NIE

提示

• $1\le d\lt n\le 2\times 10^5$；
• $1\le m\le 2\times 10^5$。
• 给定的图无重边自环。