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

// Recursive function to perform DFS
void dfs(int currentNode, const vector<vector<int>>& adjList, vector<bool>& visited) {
    // Mark the current node as visited
    visited[currentNode] = true;

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

    // Visit all unvisited neighbors of the current node
    for (int neighbor : adjList[currentNode]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adjList, visited); // Recursive call for the neighbor
        }
    }
}

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 DFS
    int startNode;
    cout << "Enter the starting node for DFS: ";
    cin >> startNode;

    // Perform DFS traversal
    vector<bool> visited(nodes, false); // Vector to keep track of visited nodes
    cout << "DFS traversal starting from node " << startNode << ": ";
    dfs(startNode, adjList, visited);

    return 0;
}