// Arup Guha
// 2/7/2023
// Illustration of how to read in a graph as a list of adjacencly lists and run DFS, BFS on it in C++

using namespace std;

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

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

void dfs(int v, int* compNum, int ID);
int* bfs(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);
    }

    // Set up looking for components.
    int numComp = 0;
    int* compNum = new int[numV];
    for (int i=0; i<numV; i++) compNum[i] = -1;

    // Run a DFS for each new component.
    for (int i=0; i<numV; i++) {
        if (compNum[i] == -1) {
            dfs(i, compNum, numComp);
            numComp++;
        }
    }

    // Store vertices in each component.
    vector< vector<int> > listOfComp(numComp);
    for (int i=0; i<numV; i++) {
        listOfComp[compNum[i]].push_back(i);
    }

    delete [] compNum;

    // Print out graph by components.
    cout << "Your graph has " << numComp << " components." << endl;
    for (int i=0; i<numComp; i++) {
        cout << "Items in component " << i << ": ";
        for (vector<int>::iterator x = listOfComp[i].begin(); x<listOfComp[i].end(); x++)
            cout << *x << ", ";
        cout << endl;
    }

    // Run a BFS from each vertex.
    for (int i=0; i<numV; i++) {
        int* dist = bfs(i);
        cout << "Here are the distance from " << i << " to each vertex." << endl;
        for (int j=0; j<numV; j++)
            cout << dist[j] << " ";
        cout << endl;

        delete [] dist;
    }

    return 0;
}

// Run a DFS on v for component # ID.
void dfs(int v, int* compNum, int ID) {
    compNum[v] = ID;
    for (vector<int>::iterator x = graph[v].begin(); x<graph[v].end(); x++)
        if (compNum[*x] == -1)
            dfs(*x, compNum, ID);
}

int* bfs(int v) {

    // Set up distances.
    int* dist = new int[numV];
    for (int i=0; i<numV; i++) dist[i] = -1;
    dist[v] = 0;

    queue<int> q;
    q.push(v);

    // Run BFS.
    while (q.size() > 0) {

        // Get next.
        int cur = q.front(); q.pop();

        // Enqueue all new neighbors.
        for (vector<int>::iterator x = graph[cur].begin(); x<graph[cur].end(); x++) {
            if (dist[*x] != -1) continue;
            q.push(*x);
            dist[*x]= dist[cur] + 1;
        }
    }

    return dist;
}