#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Function to perform BFS on the graph
void bfs(const vector<vector<int>>& adjList, int startNode) {
    // Queue to store the nodes for BFS traversal
    queue<int> q;

    // Vector to keep track of visited nodes
    vector<bool> visited(adjList.size(), false);

    // Start the BFS from the startNode
    visited[startNode] = true; // Mark the startNode as visited
    q.push(startNode);         // Push the startNode into the queue

    // Perform BFS
    while (!q.empty()) {
        // Get the front node of the queue
        int currentNode = q.front();
        q.pop(); // Remove it from the queue

        // Process the current node (here, we simply print it)
        cout << currentNode << " ";

        // Visit all neighbors of the current node
        for (int neighbor : adjList[currentNode]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true; // Mark the neighbor as visited
                q.push(neighbor);         // Add it to the queue for further exploration
            }
        }
    }
}

int main() {
    // Variables to store the number of nodes and edges
    int nodes, edges;

    // Input number of nodes and edges
    cout << "Enter the number of nodes: ";
    cin >> nodes;
    cout << "Enter the number of edges: ";
    cin >> edges;

    // Create an adjacency list for the graph
    vector<vector<int>> adjList(nodes);

    // Input all edges
    cout << "Enter the edges (format: u v for an edge between u and v):\n";
    for (int i = 0; i < edges; i++) {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v); // Add edge from u to v
        adjList[v].push_back(u); // Add edge from v to u (for undirected graph)
    }

    // Input the starting node for BFS
    int startNode;
    cout << "Enter the starting node for BFS: ";
    cin >> startNode;

    // Perform BFS traversal
    cout << "BFS traversal starting from node " << startNode << ": ";
    bfs(adjList, startNode);

    return 0;
}