Путишествия в космосе
Инфраструктура космической галактики состоит из N планет и M прямых межпланетных маршрутов , каждый из которых связывает ровно две разные планеты . Расстояния в космосе достаточно большие , поэтому, если планеты не имеют прямого сообщения , то во время перелетов используют транзитные планеты.
Популярностью планеты k будем считать количество пар различных планет i и j, перелет между которыми возможен только при использовании планеты k (i, j, k = 1..N). Для заданной системы космических сообщений найти значение максимальной популярности и количество планет, достигающих её.
Входные данные: В первой строке натуральные числа N и M ( 1<=N<=1000, 1<=M<=5000 ). В следующих M строках по два натуральных числа, описывающие маршрут между планетами i и j ( i, j = 1..N ).
Выходные данные: Ответ к задаче .