#include<iostream>
#include<vector>
#include<stack>
 
using namespace std;
 
// Function to perform Depth-First Search
void DFS(vector<vector<int>>& graph, int start, vector<bool>& visited) {
    // Stack to keep track of nodes to visit
    stack<int> stack;
 
    // Push the starting node onto the stack
    stack.push(start);
 
    // Mark the starting node as visited
    visited[start] = true;
 
    // Iterate until the stack is empty
    while (!stack.empty()) {
        // Get the top node from the stack
        int current = stack.top();
        stack.pop();
        cout << current << " "; // Process the current node
 
        // Visit all adjacent nodes
        for (int neighbor : graph[current]) {
            // If the neighbor has not been visited, mark it as visited and push it onto the stack
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                stack.push(neighbor);
            }
        }
    }
}
 
int main() {
    // Sample graph represented as an adjacency list
    vector<vector<int>> graph = {
        {1, 2},     // Node 0 is connected to nodes 1 and 2
        {0, 3, 4},  // Node 1 is connected to nodes 0, 3, and 4
        {0, 5},     // Node 2 is connected to nodes 0 and 5
        {1},        // Node 3 is connected to node 1
        {1},        // Node 4 is connected to node 1
        {2}         // Node 5 is connected to node 2
    };
 
    // Number of nodes in the graph
    int numNodes = graph.size();
 
    // Vector to keep track of visited nodes
    vector<bool> visited(numNodes, false);
 
    // Start DFS from node 0
    cout << "Depth-First Search starting from node 0: ";
    DFS(graph, 0, visited);
    cout << endl;
 
    return 0;
}

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8c3RhY2s+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gRnVuY3Rpb24gdG8gcGVyZm9ybSBEZXB0aC1GaXJzdCBTZWFyY2gKdm9pZCBERlModmVjdG9yPHZlY3RvcjxpbnQ+PiYgZ3JhcGgsIGludCBzdGFydCwgdmVjdG9yPGJvb2w+JiB2aXNpdGVkKSB7CiAgICAvLyBTdGFjayB0byBrZWVwIHRyYWNrIG9mIG5vZGVzIHRvIHZpc2l0CiAgICBzdGFjazxpbnQ+IHN0YWNrOwoKICAgIC8vIFB1c2ggdGhlIHN0YXJ0aW5nIG5vZGUgb250byB0aGUgc3RhY2sKICAgIHN0YWNrLnB1c2goc3RhcnQpOwoKICAgIC8vIE1hcmsgdGhlIHN0YXJ0aW5nIG5vZGUgYXMgdmlzaXRlZAogICAgdmlzaXRlZFtzdGFydF0gPSB0cnVlOwoKICAgIC8vIEl0ZXJhdGUgdW50aWwgdGhlIHN0YWNrIGlzIGVtcHR5CiAgICB3aGlsZSAoIXN0YWNrLmVtcHR5KCkpIHsKICAgICAgICAvLyBHZXQgdGhlIHRvcCBub2RlIGZyb20gdGhlIHN0YWNrCiAgICAgICAgaW50IGN1cnJlbnQgPSBzdGFjay50b3AoKTsKICAgICAgICBzdGFjay5wb3AoKTsKICAgICAgICBjb3V0IDw8IGN1cnJlbnQgPDwgIiAiOyAvLyBQcm9jZXNzIHRoZSBjdXJyZW50IG5vZGUKICAgICAgICAKICAgICAgICAvLyBWaXNpdCBhbGwgYWRqYWNlbnQgbm9kZXMKICAgICAgICBmb3IgKGludCBuZWlnaGJvciA6IGdyYXBoW2N1cnJlbnRdKSB7CiAgICAgICAgICAgIC8vIElmIHRoZSBuZWlnaGJvciBoYXMgbm90IGJlZW4gdmlzaXRlZCwgbWFyayBpdCBhcyB2aXNpdGVkIGFuZCBwdXNoIGl0IG9udG8gdGhlIHN0YWNrCiAgICAgICAgICAgIGlmICghdmlzaXRlZFtuZWlnaGJvcl0pIHsKICAgICAgICAgICAgICAgIHZpc2l0ZWRbbmVpZ2hib3JdID0gdHJ1ZTsKICAgICAgICAgICAgICAgIHN0YWNrLnB1c2gobmVpZ2hib3IpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIC8vIFNhbXBsZSBncmFwaCByZXByZXNlbnRlZCBhcyBhbiBhZGphY2VuY3kgbGlzdAogICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBncmFwaCA9IHsKICAgICAgICB7MSwgMn0sICAgICAvLyBOb2RlIDAgaXMgY29ubmVjdGVkIHRvIG5vZGVzIDEgYW5kIDIKICAgICAgICB7MCwgMywgNH0sICAvLyBOb2RlIDEgaXMgY29ubmVjdGVkIHRvIG5vZGVzIDAsIDMsIGFuZCA0CiAgICAgICAgezAsIDV9LCAgICAgLy8gTm9kZSAyIGlzIGNvbm5lY3RlZCB0byBub2RlcyAwIGFuZCA1CiAgICAgICAgezF9LCAgICAgICAgLy8gTm9kZSAzIGlzIGNvbm5lY3RlZCB0byBub2RlIDEKICAgICAgICB7MX0sICAgICAgICAvLyBOb2RlIDQgaXMgY29ubmVjdGVkIHRvIG5vZGUgMQogICAgICAgIHsyfSAgICAgICAgIC8vIE5vZGUgNSBpcyBjb25uZWN0ZWQgdG8gbm9kZSAyCiAgICB9OwoKICAgIC8vIE51bWJlciBvZiBub2RlcyBpbiB0aGUgZ3JhcGgKICAgIGludCBudW1Ob2RlcyA9IGdyYXBoLnNpemUoKTsKCiAgICAvLyBWZWN0b3IgdG8ga2VlcCB0cmFjayBvZiB2aXNpdGVkIG5vZGVzCiAgICB2ZWN0b3I8Ym9vbD4gdmlzaXRlZChudW1Ob2RlcywgZmFsc2UpOwoKICAgIC8vIFN0YXJ0IERGUyBmcm9tIG5vZGUgMAogICAgY291dCA8PCAiRGVwdGgtRmlyc3QgU2VhcmNoIHN0YXJ0aW5nIGZyb20gbm9kZSAwOiAiOwogICAgREZTKGdyYXBoLCAwLCB2aXNpdGVkKTsKICAgIGNvdXQgPDwgZW5kbDsKCiAgICByZXR1cm4gMDsKfQ==