Задачі
Космічні подорожі
Космічні подорожі
Інфраструктура космічної галактики складається з \textbf{N} планет та \textbf{M }прямих міжпланетних маршрутів, кожен з яких зв’язує рівно дві різні планети. Відстані в космосі досить великі, тому, якщо планети не мають прямого сполучення, то під час перельотів використовують транзитні планети.
Популярністю планети \textbf{k} будемо вважати кількість пар різних планет \textbf{i} і \textbf{j}, переліт між якими можливий тільки при використанні планети \textbf{k} (\textbf{i}, \textbf{j},\textbf{k=1..N}). Для заданої системи космічних сполучень знайти значення максимальної популярності та кількість планет, що її досягають.
\textbf{Вхідні дані}: В першому рядку натуральні числа \textbf{N }і \textbf{M }(\textbf{1<=N<=1000,1<=M<=5000}). У наступних \textbf{M }рядках по два натуральних числа, що описують маршрут між планетами \textbf{i} і \textbf{j}(\textbf{i}, \textbf{j=1..N}).
\textbf{Вихідні дані}:\textit{ }Відповідь до задачі.
Вхідні дані #1
4 4 1 2 1 3 1 4 2 3
Вихідні дані #1
5 1