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

#define inf (std::numeric_limits<int>::max())

enum color { WHITE, GRAY, BLACK };

typedef int                             Node;
typedef std::vector<std::vector<int>>   List;
typedef std::vector<color>              Colors;

void bfs(const List& neighbours, 
         Colors& color, 
         std::vector<int>& dist, 
         std::vector<Node>& pi, 
         int s) 
{
    for(Node u = 0; u < neighbours.size(); u++) {
        color[u] = WHITE;
        dist[u] = inf;
        pi[u] = -1;
    }

    color[s] = GRAY;
    dist[s] = 0;
    pi[s] = -1;

    std::queue<Node> q;
    q.push(s);
    while (!q.empty()) {
        Node u = q.front(); q.pop();
        for (Node v : neighbours[u]) {
            if (color[v] == WHITE) {
                color[v] = GRAY;
                dist[v] = dist[u] + 1;
                pi[v] = u;
                std::cout << v << std::endl;
                q.push(v);
            }
        }
        color[u] = BLACK;
    }
}

void print_path(const std::vector<Node>& pi, Node s, Node v)
{
    if (v == s) {
        std::cout << s << std::endl;
    } else if (pi[v] == -1) {
        std::cout << "No path from " << s << " to " << v << "!" << std::endl;
        exit(EXIT_FAILURE);
    } else {
        print_path(pi, s, pi[v]);
        std::cout << v << std::endl;
    }
}

int main(int argc, const char *argv[])
{
    List neighbours = {
        {1, 3},
        {0, 4},
        {4, 5},
        {0},
        {1, 2, 5},
        {2, 4}
    };

    const int n = neighbours.size();

    Colors colors(n);
    std::vector<int> dist(n);
    std::vector<Node> pi(n);

    bfs(neighbours, colors, dist, pi, 1);
    
    return 0;
}