/*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++){
		    for (int j=1;j<=n;j++)
		    	pre[j] = 0;
		    BL(i,i);
	    }
	    int maxLocal;
	    int minGlobal = 999;
	    int verticeCentro;
	    for (int k=1; k<=n; k++){
	    	cout << "Distancias para o vertice: "<< k << endl;
	    	maxLocal = 0;
	        for(i=1; i<=n; i++){
			    cout<<DM[k][i]<<" ";
			    if (maxLocal < DM[k][i]){
			    	maxLocal = DM[k][i];
			    }
	        }
	        cout << endl;
	        cout << "Distancia máxima de " << k << ": " << maxLocal << endl;
	        if (maxLocal < minGlobal){
	        	minGlobal = maxLocal;
	        	verticeCentro = k;
	        }
	    }
	    cout << "Vértice centro: " << verticeCentro << endl;
    }
	return 0;
}