Dominating the Kingdom with Improved Towers

Bytie is playing a tower defense game. His domain is represented as an undirected graph with n vertices and m edges, where each edge has a distance of 1. It is known that one can cover (i.e. dominate) the entire graph by placing at most k standard guard towers. A standard guard tower placed at a vertex u protects u and every vertex adjacent to u (i.e. at distance 1).

Now Bytie has a trick up his sleeve – he can build improved guard towers which have an extended attack range. An improved tower placed at vertex u protects a vertex v if at least one of the following holds:

• u = v (itself),
• u and v are directly connected by an edge (distance 1),
• There exists a vertex w such that u is connected to w and w is connected to v (i.e. distance 2).

Your task is to compute a set of vertices (a plan of tower placements) of size at most k such that if improved towers are built at these vertices, every vertex in the graph is protected (i.e. within distance at most 2 from one of the chosen vertices).

Note: Since any set of vertices that dominates the graph with towers of attack radius 1 is also a valid dominating set for towers with attack radius 2, the existence guarantee implies that a solution with at most k towers exists. However, finding a minimum dominating set is NP‐hard in general. In this problem, you only need to find some valid set of vertices (of size at most k) whose improved tower coverage dominates the entire graph.

The domination condition in formal LaTeX is as follows: an improved tower built at town \( u \) protects town \( v \) if and only if \[ \bigl(u = v\bigr) \quad \text{or} \quad (u,v) \in E \quad \text{or} \quad \exists\, w\;\text{such that}\; (u,w) \in E \;\text{and}\; (w,v) \in E. \]

inputFormat

The first line contains three integers n, m, and k (1 ≤ n, m ≤ 10⁵ possibly, and 1 ≤ k ≤ n) representing the number of vertices, the number of edges, and the maximum number of towers you may place.

The following m lines each contain two integers u and v (1 ≤ u, v ≤ n, u \(\ne\) v) indicating that there is a bidirectional road between towns u and v.

It is guaranteed that there is a set of at most k vertices such that each vertex in the graph is either in the set or adjacent to some vertex in the set.

outputFormat

On the first line, output an integer r (0 ≤ r ≤ k) representing the number of towers you will place. On the second line, output r space‐separated integers which are the indices of the vertices where you place the improved towers. The vertices are numbered from 1 to n. The configuration must satisfy that every vertex in the graph is within distance 2 of at least one chosen vertex.

sample

3 2 1
1 2
2 3

1
2