#include <bits/stdc++.h>
using namespace std;

//toast418
#define ffor(i,o,f)		   for(int i = o; i < f; i++)
#define pb 				   push_back
#define mp                 make_pair
#define all(a)             (a).begin(), (a).end()
#define F                  first
#define S                  second
#define PI 				   3.14159265358979323846264338327950
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl 			   '\n'
#define sz(x)              ((int)(x).size())
typedef long long          ll;
typedef pair < int, int >  pii;
typedef vector < int >     vi;
typedef vector < pii >     vii;
typedef vector < vi > 	   gi;
typedef vector < ll >      vll;
typedef map < int, int >   mii;

int t, n, m, u, v, groups;
const int tam = 1005;
gi g;
vi dist;
vi parent;
queue < int > q;

void bfs(int nd){
    dist[nd] = 0;
    parent[nd] = -1;
    q.push(nd);
    while(!q.empty()){
        nd = q.front();
        q.pop();
        ffor(i, 0, sz(g[nd])){
            int nxt = g[nd][i];
            if(dist[nxt] == -1){
                dist[nxt] = dist[nd] + 1;
                parent[nxt] = nd;
                q.push(nxt);
            }
        }
    }
}

void printPath(int nd){
    vi path;
    while(nd != -1){
        path.pb(nd);
        nd = parent[nd];
    }
    reverse(all(path));
    ffor(i, 0, sz(path)){
        if(i > 0){
            cout << " -> ";
        }
        cout << path[i];
    }
}

int main()
{
    g.assign(tam, vi ());
    dist.assign(tam, -1);
    parent.assign(tam, -1);

    g[0].pb(2);
    g[2].pb(0);
    g[0].pb(3);
    g[3].pb(0);
    g[1].pb(3);
    g[3].pb(1);
    g[1].pb(6);
    g[6].pb(1);
    g[2].pb(3);
    g[3].pb(2);
    g[2].pb(4);
    g[4].pb(2);
    g[2].pb(5);
    g[5].pb(2);
    g[4].pb(5);
    g[5].pb(4);
    g[3].pb(7);
    g[7].pb(3);
    g[6].pb(7);
    g[7].pb(6);

    bfs(0);

    ffor(i, 0, 8){
        cout << "Nodo " << i << ": ";
        if(dist[i] == -1){
            cout << "inalcanzable" << endl;
            continue;
        }
        cout << "distancia = " << dist[i] << ", ruta = ";
        printPath(i);
        cout << endl;
    }
}