e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Strong Connected Components

Компьютерная сеть

Компьютерная сеть содержит n компьютеров, пронумерованных от 0 до n - 1. Каждый из них после получения сообщения передает его другим компьютерам. Если сообщение с компьютера x может попасть на компьютер y, это не обязательно означает, что сообщение с компьютера y доходит до компьютера x. Системные администраторы хотят определить минимальное количество компьютеров, с которых должно быть отправлено сообщение, чтобы оно дошло до всех компьютеров в сети.

Для лучшей передачи сообщений они считают, что сеть необходимо расширить, добавив новые соединения между некоторыми компьютерами, поэтому при отправке сообщения с произвольного компьютера оно будет распространено среди всех остальных. Для этого необходимо определить минимальное количество добавляемых новых подключений, чтобы каждый из компьютеров можно было использовать как начальный для распространения сообщений.

Напишите программу, которая найдет минимальное количество компьютеров, с которых должно быть отправлено сообщение для распространения на все компьютеры в сети, и найдет минимальное количество новых подключений, которые необходимо добавить, чтобы сообщение, отправленное с любого компьютера, смогло дойти к любому другому компьютеру в сети.

Входные данные

Первая строка содержит два целых числа n (1n1600) и m (0m120000), задающих количество компьютеров и число связей между ними. Каждая из следующих m строк описывает одну из имеющихся связей. Первое число в ней - номер компьютера, посылающего сообщение, второе число - номер компьютера, получающего сообщение.

Выходные данные

В одной строке выведите два целых числа - минимальное количество компьютеров, которые можно использовать как начальные для распространения сообщения для всей сети, и минимальное количество дополнительных подключений, необходимых для расширения сети таким образом, чтобы сообщение, отправленное с произвольно выбранного компьютера, достигло всех остальных.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
5 6
0 1
0 3
0 2
1 3
1 4
4 0
Выходные данные #1
1 2
Входные данные #2
6 12
0 1
0 2
1 0
1 2
2 0
2 1
3 4
3 5
4 3
4 5
5 3
5 4
Выходные данные #2
2 2
Источник 2017 IX International autumn tournament in informatics, Shumen, Junior, Problem C