P3557 [POI 2013] GRA-Tower Defense Game

Bytie 正在玩一款电脑游戏 Tower Defense。 他的目标是建造守卫塔楼，以保护他的整个领地。 在 Bytie 的领地中有多个城镇，其中一些城镇通过双向道路相连。 如果 Bytie 在一个城市建造了守卫塔楼，那么这座塔楼将保护它所在的城市以及所有通过道路直接与之相连的城市。 正当 Bytie 在思考如何在他的领地上布置守卫塔楼时，他的姐姐 Bytea 走进了房间。她瞥了一眼屏幕上显示的地图，片刻之后大声说道： “嗨，这有什么好想的，显然 $k$ 座塔就足够了！” 被姐姐破坏了游戏乐趣所激怒，Bytie 把姐姐请出了门，然后开始思考接下来该怎么办。 他的自尊心不允许他建造超过 $k$ 座塔楼。 不过，他自有妙计： 他可以研发一项技术，使他能够建造升级版守卫塔楼。 一座升级版守卫塔楼不仅能保护它所在的城镇及其直接相邻的城镇，还能保护更远距离的城镇。 具体来说，如果满足以下任一条件，则建在城镇 $u$ 的升级版守卫塔楼将保护城镇 $v$： - $u = v$； - 存在一条从 $u$ 直接通往 $v$ 的道路； - 或者存在一个城镇 $w$，使得存在从 $u$ 到 $w$ 的直接道路和从 $w$ 到 $v$ 的直接道路。 当然，Bytie 仍然努力最多只建造 $k$ 座塔楼，但他现在对这些塔楼是升级版守卫塔楼毫无顾虑。

标准输入的第一行包含三个整数 $n$、$m$ 和 $k$（$2\le n\le 500\ 000$，$0\le m\le 1\ 000\ 000$，$1\le k\le n$），它们以单个空格分隔，分别表示 Bytie 领地中的城镇数量、道路数量，以及 Bytea 给定的数值 $k$。 Bytie 领地中的城镇编号为 1 至 $n$。 接下来是 $m$ 行道路描述。 每行包含两个整数 $a_i$ 和 $b_i$（$1\le a_i,b_i\le n$，$a_i \ne b_i$），表示编号为 $a_i$ 和 $b_i$ 的城镇间存在双向道路直接相连。任意两座城镇之间至多由一条道路连接。

你的程序需要向标准输出打印两行内容，描述升级版守卫塔楼在 Bytie 领地中的部署方案： 第一行输出整数 $r$（$1\le r\le k$），表示 Bytie 应建造的升级版守卫塔楼数量。 第二行通过提供 $r$ 个两两不同的整数来指定塔楼部署位置，这些整数即建造升级版守卫塔楼的城镇编号。 城镇编号可以按任意顺序输出。 若存在多种可行方案，输出任意一种即可。 需特别说明：任意不超过 $k$ 座升级版塔楼的部署方案均可接受——你无需最小化塔楼数量。 你可以默认 Bytea 的判断是正确的，即 Bytie 的整个领地确实能被 $k$ 座普通（非升级版）守卫塔楼保护。因此本题始终存在可行解。