Wave traversal of a graph
Let the distance from vertex u to vertex v be defined as the minimum number of edges in the path connecting u and v. Therefore, the distance from u to itself is 0, and the distance between any two directly connected vertices is 1.
A wave traversal of a graph starting from vertex v is a sequence of vertices u_1, u_2, ..., u_r that satisfies the following conditions:
u_1 = v,
Every vertex in the graph that can be reached from v appears at least once in the sequence, and
Each vertex in the sequence is at least as far from v as the previous vertex.
You are given a connected undirected graph and a starting vertex v. Your task is to output any wave traversal of this graph.
Input
The first line of the input contains three numbers N, M, and v, separated by spaces. These represent the number of vertices, the number of edges in the graph, and the starting vertex for the traversal, respectively (1 ≤ N ≤ 100, 0 ≤ M ≤ 10000, 1 ≤ v ≤ N). The next M lines each contain two numbers u_i and v_i, separated by spaces (1 ≤ u_i, v_i ≤ N), indicating that there is an edge between vertices u_i and v_i.
Output
On the first line of the output, print the number r, which is the number of vertices in the wave traversal found (1 ≤ r ≤ 10000; it is guaranteed that a valid traversal exists). On the second line, print the sequence of vertices u_1, u_2, ..., u_r, separated by spaces.