ej1

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

#define INF (2 << 22)

using namespace std;
struct info
{
    int color;
    int d;
    int padre;
};
struct Arista
{
    int a, b;
};

vector<vector<int> > adj;
vector<vector<info> > datos;
vector<Arista> aristas;
bool perteneceAlTree (int raiz, Arista arista)
{
    return (datos[raiz][arista.b].padre == arista.a || datos[raiz][arista.a].padre == arista.b);
}

bool distintoNivel(int raiz, Arista arista)
{
    return (datos[raiz][arista.a].d > datos[raiz][arista.b].d || datos[raiz][arista.a].d < datos[raiz][arista.b].d);
}

void BFS(int nodos, int &nodoInicial, int &nodoDestino, int &nodoIntermedio)
{
    queue<int>cola;
    for(int raiz = 0; raiz < nodos; raiz++)
    {
        cola.push(raiz);
        while(cola.size() != 0)
        {
            int actual = cola.front();
            for(auto v: adj[actual])
            {
                if(datos[raiz][v].color == 0)
                {
                    datos[raiz][v].color = 1;
                    datos[raiz][v].d = datos[raiz][actual].d + 1;
                    datos[raiz][v].padre = actual;
                    cola.push(v);
                }
            }
            datos[raiz][actual].color = 2;
            cola.pop();
        }
        if(nodoInicial == -1 && nodoDestino == -1)
        {
            for(auto arista: aristas)
            {
                if(!perteneceAlTree(raiz, arista) && distintoNivel(raiz, arista))
                {
                    nodoInicial = raiz;
                    nodoIntermedio = (datos[raiz][arista.a].d < datos[raiz][arista.b].d) ? arista.a : arista.b;
                    nodoDestino = (datos[raiz][arista.a].d > datos[raiz][arista.b].d) ? arista.a : arista.b;
                }
            }
        }

    }
}

void imprimirCamino(int nodoInicial, int nodoDestino)
{
    if(nodoInicial == nodoDestino)
        cout << nodoInicial << " ";
    else
    {
        imprimirCamino(nodoInicial, datos[nodoInicial][nodoDestino].padre);
        cout << nodoDestino <<" ";
    }
}

void mostrarCaminosMinimos(int nodos)
{
    cout << 1 << endl;
    for(int f = 0; f < nodos; f++)
        {
        for(int c = 0; c < nodos; c++)
        {
            cout << datos[f][c].padre << " ";
        }
        cout << endl;
        }
}

void mostrarDosCaminos(int nodoInicial, int nodoIntermedio, int nodoDestino)
{
    cout << 0 << endl;
    imprimirCamino(nodoInicial, nodoDestino);
    cout << endl;
    imprimirCamino(nodoInicial, nodoIntermedio);
    cout << nodoDestino << endl;
}
int main()
{
    int n, m;
    cin >> n >> m;
    //redimension del vector de adyacencias y la matriz de distancias, color y predecesores
    adj.resize(n);
    datos.resize(n, vector<info> (n, {0,INF, -1}));
    int a, b;
    //entrada del vector de adyacencias
    for(int i = 0; i < m; i++)
    {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        aristas.push_back({a,b});
    }
    //inicialización de cada nodo desde donde comenzara el BFS
    for(int i = 0; i < n; i++)
        datos[i][i] = {1, 0, i};

    int nodoInicial = -1, nodoDestino = -1, nodoIntermedio = -1;
    BFS(n, nodoInicial, nodoDestino, nodoIntermedio);

    if(nodoInicial == -1 && nodoDestino == -1)
        mostrarCaminosMinimos(n);
    else mostrarDosCaminos(nodoInicial, nodoIntermedio, nodoDestino);
    return 0;
}