e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

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

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

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

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

Time limit 1 second
Memory limit 64 MiB
Input example #1
4 4
1 2
1 3
1 4
2 3
Output example #1
5 1
Source Житомирская ХХVIII обласная олимпиада по информатике