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