eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Склеювання

Склеювання

Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB

Задано орієнтованиый граф, вершини в якому пронумеровані числами від 1 до N. У ньому дозволяється виконувати операцію склеювання двох вершин, яка полягає в тому, що з графа видаляються дві вершини і додається одна нова вершина, в яку йдуть дуги з тех вершин, з яких були дуги хоча б в одну з видалених вершин, та з якої йдуть дуги у всі вершини, куди йшли дуги хоча б з однієї з видалених вершин. Нова вершина отримує в якості свого номера мінімальний з номерів склеюваних вершин. Потрібно за найменшу кількість операцій склеювання добитись того, щоб в графі з довільної вершини можна було попасти в довільну іншу.

Вхідні дані Перший рядок вхідного файлу містить цілі числа N та M — кількість вершин та дуг в заданому графі (1N200). Наступні M рядків містять опис дуг, кажен з яких задано номером початкової та кінцевої вершини. Граф не містить петель та кратних ребер. Вихідні дані У вихідний файл виведіть K — число операцій склеювання.

Приклад

Вхідні дані #1
4 4
1 2
4 3
1 3
4 2
Вихідні дані #1
2