Комп'ютерна мережа#8553
Комп'ютерна мережа містить комп'ютерів, пронумерованих від до n - 1. Кожний з них після отримання повідомлення передає його іншим комп'ютерам. Якщо повідомлення з комп'ютера може потрапити на комп'ютер , це не обов'язково означає, що повідомлення з комп'ютера доходить до комп'ютера . Системні адміністратори хочуть визначити мінімальну кількість комп'ютерів, з яких має бути відправлено повідомлення, щоб воно дійшло до всіх комп'ютерів у мережі.
Для кращої передачі повідомлень адміністратори вважають, що мережу необхідно розширити, додавши нові з'єднання між деякими комп'ютерами, так, щоб при відправленні повідомлення з довільного комп'ютера воно поширювалося серед всіх інших. Для цього необхідно визначити мінімальну кількість нових підключень, щоб кожний з комп'ютерів мережі міг би бути першим, з якого поширюватиметься повідомлення.
Напишіть програму, яка знайде мінімальну кількість комп'ютерів, з яких має бути відправлено повідомлення для поширення на всі комп'ютери мережі, і знайде мінімальну кількість нових підключень, які необхідно додати, щоб повідомлення, відправлене з будь-якого комп'ютера, змогло дійти до будь-якого іншого комп'ютера в мережі.
Перший рядок містить два цілих числа n~(1 \le n \le 1600) та m~(0 \le m \le 120000), які задають кількість комп'ютерів та число каналів зв'язку між ними. Кожний із наступних рядків описує один із наявних каналів зв'язку. Перше число — номер комп'ютера, який відправляє повідомлення, друге число — номер комп'ютера, який отримує повідомлення.
В одному рядку виведіть два цілих числа — мінімальну кількість комп'ютерів, які можна використовувати як початкові для поширення повідомлення для всієї мережі, і мінімальну кількість додаткових підключень, необхідних для розширення мережі таким чином, щоб повідомлення, відправлене з довільного комп'ютера, досягло всіх інших.
Приклад 1
Приклад 2