Node Visit Order
Given an undirected graph, print the order in which nodes are visited by a Breadth-First Search (BFS) starting from node 1. Assume nodes are numbered from 1 to N. If a node is visited multiple times, print it only the first time it is encountered. The BFS should explore neighbors in increasing order of their node numbers.
Input
The first line contains two integers N and M, the number of nodes and edges respectively. The next M lines each contain two integers u and v, representing an undirected edge between node u and node v.
Output
Print N integers on a single line, separated by spaces, representing the order of visited nodes.
Constraints
1 <= N <= 1000 0 <= M <= N*(N-1)/2
Example 1
4 3 1 2 1 3 2 4
1 2 3 4
BFS starts at 1. Neighbors of 1 are 2 and 3. Explore 2 first. Neighbors of 2 are 1 and 4. Explore 4. Neighbors of 3 are 1. Explore 3.
Example 2
5 5 1 2 1 3 2 4 3 4 4 5
1 2 3 4 5
BFS starts at 1. Visit order: 1, 2, 3, 4, 5.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 3 1 2 1 3 2 4
5 5 1 2 1 3 2 4 3 4 4 5