Tower Defense Game

Bytie is playing a computer game called Tower Defense. He wants to build guard towers so that they protect his whole domain. The domain has several towns, and some pairs of towns are joined by two-way roads. A guard tower built in a town protects that town and every town joined to it by a road.

Bytie was still thinking about where to put the towers when his older sister Bytea walked in. She glanced at the map on the screen and said: "What is there to think about? $k$ towers are clearly enough."

Bytie sent her out of the room for spoiling the fun and started planning his next move. His pride will not let him build more than $k$ towers. He does have one card left to play. He can research a technology for improved guard towers, which reach further than the ordinary ones. Precisely, an improved guard tower built in town $u$ protects town $v$ when one of the following holds:

• $u = v$;
• a road joins $u$ and $v$ directly;
• some town $w$ has a road to $u$ and a road to $v$.

Bytie still wants at most $k$ towers, but he has no objection to making all of them improved ones.

The first line contains three integers $n$, $m$, and $k$ ($2 \le n \le 500\,000$, $0 \le m \le 1\,000\,000$, $1 \le k \le n$), separated by single spaces. They are the number of towns, the number of roads, and the number $k$ that Bytea named.

The towns are numbered from $1$ to $n$. Each of the next $m$ lines describes one road and contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$), meaning that towns $a_i$ and $b_i$ are joined by a two-way road. At most one road joins any pair of towns.

Many placements satisfy the requirement, so Bytie fixed one of them as a rule in advance. He walks through the towns in increasing order of number, and whenever he reaches a town that none of the towers built so far protects, he builds an improved guard tower there. He builds nothing in a town that is already protected.

Print two lines. The first line holds $r$, the number of towers this rule builds. The second line holds the numbers of those $r$ towns in increasing order, separated by single spaces.

You may assume that Bytea was right, that is, $k$ plain guard towers really can protect the whole domain. The rule above then never builds more than $k$ towers, so $1 \le r \le k$ always holds.