/*Neste programa você vai trabalhar com a Busca em Largura (BFS) em um grafo 
   simples, usando a representação de matriz de adjacências.
1. A idéia é determinar a matriz de distâncias mínimas DM entre todos 
   os vértices do grafo e com isso determinar o centro do grafo. O centro do grafo
   é um conjunto de vértices que têm a distância máxima a eles mínima.
2. Modifique o programa para determinar toda a matriz de distâncias mínimas
   e determinar o centro do grafo.
*/
#include<iostream>
#include <string.h>
using namespace std;
const int NVM=1001;
typedef struct no{int v;  int d;};

// Declarações para o grafo
int n, m, cpre, pre[NVM], E[NVM][NVM], DM[NVM][NVM];

//Outras declarações
int i, j, u, w, f, r;
no  Q[NVM];

void Inicializa(int n){
    memset(E, 0, sizeof(E));
    memset(DM, 0, sizeof(DM));    
    memset(pre, 0, sizeof(pre));
	f = r = cpre = 0;
}
void BL(int u, int v){
	no t;
	pre[v] = ++cpre; r = 1; f = 1; Q[1].v = v;  Q[1].d = 0; 
	while(f != 0){
		t = Q[f];
		for(int w=1; w<=n; w++)
			if( (E[w][t.v] == 1) && (pre[w] == 0)){
				r++; Q[r].v = w;  Q[r].d = t.d+1; pre[w] = ++cpre;
				DM[v][w] = t.d+1;
			}
		if(f == r) f = 0;
		else       f++;
	}
}

int main(){   
	cout<<endl<<"n m = ";
	 while (cin >> n >> m){
         //cout<<endl<<"n m = ";  cin >> n >> m;
	     Inicializa(n);
	     cout<<"Arestas:"<<endl;
         for(i=1; i<=m; i++){
              cin >>u>>w; 
              E[u][w] = E[w][u] = 1;
         }
	    for(i=1; i<=n; i++)
		    if(pre[i] == 0)
			    BL(i,i);
	    cout << "Distancias para o vertice 1:"<<endl;
        for(i=1; i<=n; i++)
		    cout<<DM[1][i]<<" ";			    
    }
	return 0;
}