#include <stdio.h>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
int peoplesz;
int linksz;
void queuefunc(int n);
int cnt[101][101];
int minv[101][101];
vector<int> link[101];
int isgroup[101];
vector<int> group[101];
int groupn;
int total [101];
bool islink[101][101];
int main(void) {
FILE *rt = fopen("input.txt","rt");
FILE *wt = fopen("output.txt","wt");
fscanf(rt,"%d\n%d\n",&peoplesz,&linksz);
for(int i = 0; i<101; i++) {
for(int j = 0; j<101; j++) {
minv[i][j] = 1000000000;
cnt[i][j] = 100000000;
}
}
for(int i = 0; i<linksz; i++) {
int n1,n2;
fscanf(rt,"%d %d\n",&n1,&n2);
islink[n1][n2] = true;
islink[n2][n1] = true;
link[n1].push_back(n2);
link[n2].push_back(n1);
}
for(int i = 1; i<=peoplesz; i++) {
queuefunc(i);
}
for(int i = 1; i<=peoplesz; i++) {
for(int j = 1; j<=peoplesz; j++) {
total[i] += (minv[i][j] == 1000000000 ? 0 : minv[i][j]);
}
}
fprintf(wt,"%d\n",groupn);
for(int i = 1; i<=groupn; i++) {
vector<int> v;
int min = 2147483647;
for(int j = 0; j<group[i].size(); j++) {
if(total[group[i][j]] < min) {
v.clear();
v.push_back(group[i][j]);
min = total[group[i][j]];
}else if(total[group[i][j]] == min){
v.push_back(group[i][j]);
}
}
if(v.size() > 1) {
min = 10000000000;
for(int j = 0; j<v.size() ;j++) {
if(min > v[j]) {
min = v[j];
}
}
fprintf(wt,"%d\n",min);
}else {
fprintf(wt,"%d\n",v[0]);
}
}
}
void queuefunc(int n) {
queue<int> next;
next.push(n);
int groupnum = (isgroup[n] == 0 ? ++groupn:isgroup[n]);
if(groupnum != isgroup[n]) {
group[groupnum].push_back(n);
}
isgroup[n] = groupnum;
minv[n][n] = 1000000000;
cnt[n][n] = 0;
while(!next.empty()) {
int m = next.front();
next.pop();
if(isgroup[m] == 0) {
isgroup[m] = groupnum;
group[groupnum].push_back(m);
}
for(int i = 0; i<link[m].size(); i++) {
if(cnt[n][link[m][i]] > cnt[n][m]+1){
cnt[n][link[m][i]] = cnt[n][m]+1;
next.push(link[m][i]);
minv[n][link[m][i]] = cnt[n][m]+1;
}
}
}
}
4,5번은 틀리다고 나오네요...ㅜㅜ
