记录编号	376070	评测结果	AAAAAAAAAA
题目名称	[Ural 1569] Iset塔上的网络	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.056 s
提交时间	2017-02-26 16:23:36	内存使用	0.35 MiB

//KZNS
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define Nmax 103
int N, M;
int gp[Nmax][Nmax];
void init() {
	scanf("%d %d", &N, &M);
	int a, b;
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		gp[a][b] = 1;
		gp[b][a] = 1;
	}
}
int mp[Nmax][Nmax];
#define INF 100000
int v1, v2;
int dis = INF;
void ck(int a, int b) {
	int ad;
	if (a == b)
		ad = 0;
	else
		ad = 1;
	int d = 0;
	for (int i = 1; i <= N; i++)
		d = max(d, 2*min(gp[a][i], gp[b][i]) + ad);
	if (d < dis) {
		v1 = a;
		v2 = b;
		dis = d;
	}
}
bool lsd[Nmax];
int fm[Nmax];
void BFS() {
	queue<int> ls;
	ls.push(v1);
	lsd[v1] = true;
	if (v2 != v1) {
		ls.push(v2);
		lsd[v2] = true;
	}
	int x;
	while (!ls.empty()) {
		x = ls.front();
		ls.pop();
		for (int i = 1; i <= N; i++) {
			if (gp[x][i] == 1 && !lsd[i]) {
				ls.push(i);
				lsd[i] = true;
				fm[i] = x;
			}
		}
	}
}
void work() {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (i != j && !gp[i][j])
				gp[i][j] = INF;
	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				gp[i][j] = min(gp[i][j], gp[i][k] + gp[k][j]);
	for (int i = 1; i <= N; i++)
		for (int j = i; j <= N; j++)
			if (gp[i][j] <= 1)
				ck(i, j);
	BFS();
	for (int i = 1; i <= N; i++)
		if (fm[i])
			printf("%d %d\n", i, fm[i]);
	if (v1 != v2)
		printf("%d %d\n", v1, v2);
}
int main() {
	freopen("iset.in", "r", stdin);
	freopen("iset.out", "w", stdout);
	init();
	work();
	return 0;
}
//UBWH