#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <utility>
#include <queue>
#include <unordered_set>

std::vector<std::vector<int>> MakeMatrix(std::string fisier, bool neorientat)
{
    std::ifstream file(fisier);

    if (file.is_open())
    {
        std::string line;
        std::getline(file, line);
        std::stringstream ss(line);
        int noduri, muchii;
        ss >> noduri >> muchii;

        int linie, coloana;
        std::vector<std::vector<int>> matrice(noduri, std::vector<int>(noduri, 0));

        if (neorientat)
        {
            for (int i = 0; i < muchii; i++)
            {
                std::getline(file, line);
                std::stringstream ss(line);
                ss >> linie >> coloana;
                matrice[linie - 1][coloana - 1] = 1;
                matrice[coloana - 1][linie - 1] = 1;
            }
        }
        else
        {
            for (int i = 0; i < muchii; i++)
            {
                std::getline(file, line);
                std::stringstream ss(line);
                ss >> linie >> coloana;
                matrice[linie - 1][coloana - 1] = 1;
            }
        }

        file.close();
        return matrice;
    }
    else
    {
        std::cout << "!Eroare la deschiderea fisierului!\n";
        exit(1);
    }
}

void PrintMatrix(std::vector<std::vector<int>> matrice)
{
    int noduri = matrice.size();

    for (int i = 0; i < noduri; i++)
    {
        for (int j = 0; j < noduri; j++)
        {
            std::cout << matrice[i][j] << ' ';
        }
        std::cout << '\n';
    }
    std::cout << '\n';
}

std::vector<std::vector<int>> MakeList(std::string fisier, bool neorientat)
{
    std::ifstream file(fisier);

    if (file.is_open())
    {
        std::string line;
        std::getline(file, line);
        std::stringstream ss(line);
        int noduri, muchii;
        ss >> noduri >> muchii;


        std::vector<std::vector<int>> liste(noduri);

        int origine, destinatie;

        if (neorientat)
        {
            for (int i = 0; i < muchii; i++)
            {
                std::getline(file, line);
                std::stringstream ss(line);
                ss >> origine >> destinatie;
                liste[origine - 1].push_back(destinatie);
                liste[destinatie - 1].push_back(origine);
            }
        }
        else
        {
            for (int i = 0; i < muchii; i++)
            {
                std::getline(file, line);
                std::stringstream ss(line);
                ss >> origine >> destinatie;
                liste[origine - 1].push_back(destinatie);
            }
        }

        file.close();
        return liste;
    }
    else
    {
        std::cout << "!Eroare la deschiderea fisierului!\n";
        exit(1);
    }
}

void PrintList(std::vector<std::vector<int>> list)
{

    for (int i = 0; i < list.size(); i++)
    {
        std::cout << i + 1 << ": ";
        for (int j = 0; j < list[i].size(); j++)
        {
            std::cout << list[i][j] << ' ';
        }
        std::cout << '\n';
    }
    std::cout << '\n';
}

std::vector<std::vector<int>> ListToMatrix(std::vector<std::vector<int>> list)
{
    int noduri = list.size();
    std::vector<std::vector<int>> matrice(noduri, std::vector<int>(noduri, 0));
    int linie;

    for (int i = 0; i < noduri; i++)
    {
        linie = i;
        for (int j = 0; j < list[i].size(); j++)
        {
            matrice[linie][list[i][j] - 1] = 1;
        }
    }

    return matrice;
}

std::vector<std::vector<int>> MatrixToList(std::vector<std::vector<int>> matrice)
{
    int noduri = matrice.size();
    std::vector<std::vector<int>> liste(noduri);

    for (int i = 0; i < noduri; i++)
    {
        for (int j = 0; j < noduri; j++)
        {
            if (matrice[i][j])
            {
                liste[i].push_back(j + 1);
            }
        }
    }

    return liste;
}

void distantaBFS(std::vector<std::vector<int>> matrice, int startNode, std::vector<int>& visited, int distanta = 1)
{
    int numNodes = matrice.size();

    // Coada pentru BFS
    std::vector<int> q;

    int currentNode = startNode - 1;

    if (visited[startNode - 1] == -1)
    {
        visited[startNode - 1] = 0;
        q.push_back(startNode - 1);
        int currentNode = q[0];
    }

    for (int i = 0; i < numNodes; i++)
    {
        if (matrice[currentNode][i] == 1 && visited[i] == -1)
        {
            visited[i] = distanta;
            q.push_back(i + 1);
        }
    }

    distanta++;

    if (!q.empty())
    {
        for (int i = 0; i < q.size(); i++)
        {
            distantaBFS(matrice, q[i], visited, distanta);
        }
    }
    else
    {
        return;
    }
}

int main()
{
    //B1a
    // iau nodul de incepere
    std::ifstream file("bfs.in");
    int s;
    if (file.is_open())
    {
        for (int i = 0; i < 3; i++)
        {
            file >> s;
        }

        file.close();
    }
    // construiesc matricea de adiacenta
    std::vector<std::vector<int>> m = MakeMatrix("bfs.in", false);
    PrintMatrix(m);
    int numNodes = m.size();

    std::vector<int> visited(numNodes, -1); // Vector pentru a nodurile vizitate

    distantaBFS(m, s, visited);

    std::ofstream out("bfs.out");

    for (int i = 0; i < numNodes; i++)
    {
        out << visited[i] << ' ';
    }

    out.close();

    return 0;
}