// Arup Guha
// 6/2/2026
// Illustration of how to read in a graph as a list of adjacencly lists and run DFS on it in C++

using namespace std;

#include <iostream>
#include <vector>
#include <queue>

int numV;
vector< vector<int> > graph;

void dfs(int v, vector<int>& compNum, vector<int>& items, int ID);
void print(vector<int>& v);

int main() {

    int numE, v1, v2;
    cin >> numV >> numE;
    graph.resize(numV);

    // Read in the edges - add both ways.
    for (int i=0; i<numE; i++) {
        cin >> v1 >> v2;
        graph[v1-1].push_back(v2-1);
        graph[v2-1].push_back(v1-1);
    }

    // compNum[i] will store which connected component vertex i is in.
    int numComp = 0;
    vector<int> compNum(numV, -1);

    vector<vector<int>> compList;

    // Run a BFS from each vertex.
    for (int i=0; i<numV; i++) {

        // We've visited this before.
        if (compNum[i] != -1) continue;

        // Store all items in this component here.
        vector<int> items;
        dfs(i, compNum, items, numComp);

        // Update for the next component.
        numComp++;

        // Add to component list.
        compList.push_back(items);
    }

    // Print the compNum vector.
    cout << "compNum vector = ";
    print(compNum);

    // Print each component.
    for (int i=0; i<numComp; i++) {
        cout << "component # " << i << " ";
        print(compList[i]);
    }

    return 0;
}

void dfs(int v, vector<int>& compNum, vector<int>& items, int ID) {

    // Mark which component v is in.
    compNum[v] = ID;
    items.push_back(v);

    // Go through neighbors.
    for (int next: graph[v]) {

        // Been visited.
        if (compNum[next] != -1) continue;

        // Recursively mark everything unvisited connected to next.
        dfs(next, compNum, items, ID);
    }
}

// Prints out the contents of a vector.
void print(vector<int>& v) {
    for (int x: v)
        cout << x << " ";
    cout << endl;
}