题目描述

题目译自 XX Olimpiada Informatyczna — III etap Gra Tower Defense

Bajtuś 正沉迷于电脑塔防游戏。他的任务是建造瞭望塔，守护整个国家。Bajtuś 的国家有许多城市，部分城市间由双向道路连接。若在某城市建造瞭望塔，它将守护该城市及所有与之直接相连的城市。

正当 Bajtuś 苦思如何布置瞭望塔时，他的姐姐 Bajtunia 闯进房间。她瞥了一眼屏幕上的国家地图，随口说道：「这有什么好想的，$k$ 座塔就够了！」Bajtuś 被姐姐打断兴致，气恼地将她赶出房间，但也开始认真思考。出于荣誉感，他决定不超过 $k$ 座塔。为此，他想到一个秘密武器：研发新技术，建造升级版瞭望塔。升级版瞭望塔不仅守护所在城市及直接相邻城市，还能覆盖更远城市。形式上，若在城市 $u$ 建造升级版瞭望塔，它守护城市 $v$，当满足以下任一条件：

• $u = v$；
• $u$ 与 $v$ 间有直接道路；
• 存在城市 $w$，使得 $u$ 到 $w$ 和 $w$ 到 $v$ 均有直接道路。

当然，Bajtuś 仍需建造至多 $k$ 座升级版瞭望塔。请帮助他规划塔的布置。

输入格式

第一行包含三个整数 $n, m, k$ $(2 \leq n \leq 500000, 0 \leq m \leq 1000000, 1 \leq k \leq n)$，分别表示 Bajtuś 国家的城市数、道路数和 Bajtunia 提到的塔数。城市编号为 $1$ 至 $n$。

接下来的 $m$ 行描述道路，每行包含两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n, a_i \neq b_i)$，表示城市 $a_i$ 和 $b_i$ 间存在双向道路。每对城市间至多有一条道路。

输出格式

输出两行，描述 Bajtuś 国家中升级版瞭望塔的布置。

第一行包含一个整数 $r$ $(1 \leq r \leq k)$，表示需建造的升级版瞭望塔数量。

第二行包含 $r$ 个两两不同的整数，表示建造升级版瞭望塔的城市编号，顺序任意。

若存在多种解法，输出任意一种即可。注意，只需输出使用不超过 $k$ 座升级版瞭望塔的布置，无需最小化塔数。题目保证 Bajtunia 的判断正确，即使用 $k$ 座普通（非升级）瞭望塔可守护整个国家，因此解始终存在。

9 8 3
1 2
2 3
3 4
1 4
3 5
4 6
7 8
8 9

3
1 5 7

附加样例

1. $n=10, m=10, k=5$，道路网络形成环。
2. $n=1414, m=998991, k=100$，每对城市均有道路，注意此时仅需 $1$ 座塔。
3. $n=500000, m=499999, k=250000$，道路网络形成路径。