Wave traversal of a graph#1392
Let the distance from vertex to vertex be defined as the minimum number of edges in a path between and . Thus, the distance from to itself is , and the distance between any two distinct adjacent vertices is .
A wave traversal of a graph from vertex is a sequence of vertices u_1, u_2, \ldots, u_r such that:
u_1 = v,
Every vertex in the graph that can be reached from appears at least once in this sequence,
Each subsequent vertex in the sequence is at a distance from that is not less than the distance to the previous vertex.
A connected undirected graph and a vertex in this graph are given. Output any wave traversal of this graph.
The first line contains three space-separated integers , , and — the number of vertices, the number of edges in the graph, and the starting vertex for the traversal (1 \leq N \leq 100, 0 \leq M \leq 10000, 1 \leq v \leq N). The next lines each contain two integers u_i and v_i (1 \leq u_i, v_i \leq N), indicating an edge between vertices u_i and v_i.
In the first line, print the number — the number of vertices in the wave traversal found (1 \leq r \leq 10000; a valid traversal exists under these constraints). In the second line, print the sequence of vertices u_1, u_2, \ldots, u_r, separated by spaces.
Example 1