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

#include <algorithm>

using namespace std;

int main(){

  //  freopen("t.txt", "r", stdin);

    int nodes, edges;
    cin >> nodes >> edges;

    vector<vector<int>> graph(nodes + 1);

    vector<int> distance(nodes + 1, -1);
    vector<int> parent(nodes + 1);
    vector<int> shortestPath;

    queue<int> bfs;

    while(edges--){
       int from, to;
       cin >> from >> to;

       graph[from].push_back(to);
       graph[to].push_back(from);
    }

    int src = 1;
    bfs.push(src);
    distance[src] = 0;
    parent[src] = src;


    while(!bfs.empty()){
        int node = bfs.front();
        bfs.pop();

        for(int child : graph[node]){
            if(distance[child] == -1){
                bfs.push(child);

                distance[child] = distance[node]+1;
                parent[child] = node;
            }
        }


    }
    cout << '\n';
    for(int node = 1; node <= nodes; node++)
        cout << node <<" -> "<< distance[node] <<" Parent : "<< parent[node] <<'\n';


    int dist = 7;

    cout <<"\nThe Shortest Path from "<< src <<" to "<< dist <<" is : ";

    shortestPath.push_back(dist);
    do{
        dist = parent[dist];
        shortestPath.push_back(dist);
    }while(dist != src);

    reverse(shortestPath.begin(), shortestPath.end());

    for(int node : shortestPath)
        cout << node <<' ';

    cout <<"\nand The distance of Path is : "<< distance[shortestPath[shortestPath.size()-1]] <<'\n';


}