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 обласна олімпіада з інформатики