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

Strong Connected Components

Комп'ютерна мережа

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

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

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

Вхідні дані.

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

Вихідні дані.

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

prb8553.gif

Ліміт часу 2 секунди
Ліміт використання пам'яті 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