eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Путишествия в космосе

Путишествия в космосе

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Инфраструктура космической галактики состоит из 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 ).

Выходные данные: Ответ к задаче .

Пример

Входные данные #1
4 4
1 2
1 3
1 4
2 3
Выходные данные #1
5 1
Источник Житомирская ХХVIII обласная олимпиада по информатике