оформи необычную задачу на тему Графы

Задача: Графы и сами себе на встречу

Представьте, что в городе существует сеть из N перекрестков (вершин) и M дорог (ребер), которые соединяют эти перекрестки. Весь город изображен в виде неориентированного графа, где каждый перекресток — это вершина, а каждая дорога — это ребро.

Во время фестиваля "Ночь Графов" все жители хотят встретиться на одном из перекрестков, но у каждого из них есть свои предпочтения по выбору места — они хотят собраться на перекрестке, который является "центром" города. Центр определяется как вершина, у которой минимальное максимальное расстояние до других перекрестков (то есть "центр" — это вершина с минимальным значением диаметра).

Задача:

1. Напишите программу, которая принимает на вход количество перекрестков N, количество дорог M и сами дороги в виде пар (A, B) — где A и B — это номера соединённых перекрестков.
2. Программа должна вывести номера всех перекрестков, которые могут считаться центрами, а также расстояние до самого удалённого перекрестка от каждого из этих центров.

Дополнительные условия:

• Если нескольких перекрестков имеют одинаковые расстояния, выведите их в порядке возрастания.
• Если граф несвязный, сообщите, что центр не может быть определён.

Пример входных данных:

5 6
1 2
1 3
2 3
2 4
4 5
3 5

Пример выходных данных:

Центры: 2 3
Расстояния до самого удалённого перекрестка от центра 2: 2
Расстояния до самого удалённого перекрестка от центра 3: 2

Эта задача не только проверяет знания о графах, но и требует применения алгоритмов, таких как BFS или DFS, для поиска расстояний между вершинами.