Breadth-First Search (BFS) Graph Traversal

This problem requires you to implement the Breadth-First Search (BFS) traversal on an undirected graph represented by an adjacency list. Given a starting vertex, you are to traverse the graph using the BFS algorithm and output the order in which the vertices are visited.

Algorithm Overview:

• BFS starts at the given starting vertex and explores all its adjacent vertices (neighbors) level by level.
• A queue is used to determine the vertices to be processed next, and a visited set is maintained to avoid processing a vertex more than once.

Edge Cases:

• If the graph is empty or the starting vertex does not exist in the graph, output an empty string.

Input/Output:

You are required to read from standard input and output the result to standard output.

Note: If a vertex is listed without any neighbors, it is assumed to be isolated.

inputFormat

The input is read from standard input (stdin) and has the following format:

<starting_vertex>
<N>
<vertex1>: <neighbor1> <neighbor2> ...
<vertex2>: <neighbor1> <neighbor2> ...
...
<vertexN>: <neighbor1> <neighbor2> ...

"<starting_vertex>" is the vertex from which BFS starts. "<N>" is the number of vertices in the graph. Each of the next N lines describes a vertex and its neighbors separated by space. If a vertex has no neighbors, only the vertex name and a colon are provided.

For example:

A
6
A: B C
B: A D E
C: A F
D: B
E: B F
F: C E

outputFormat

The output should be a single line containing the vertices in the order they are visited by the BFS traversal, separated by a single space. If the starting vertex does not exist or no traversal is possible, output an empty string.

For the sample input above, the correct output is:

A B C D E F

## sample

A
6
A: B C
B: A D E
C: A F
D: B
E: B F
F: C E

A B C D E F