Problems
Bonding (RU)
Bonding (RU)
Дан ориентированный граф, вершины в котором занумерованы числами от \textbf{1} до \textbf{N}. В нем разрешается выполнять операцию склейки двух вершин, которая заключается в том, что из графа удаляются две вершины и добавляется одна новая вершина, в которую идут дуги из тех вершин, из которых были дуги хотя бы в одну из удаленных вершин, и из которой идут дуги во все вершины, куда шли дуги хотя бы из одной из удаленных вершин. Новая вершина получает в качестве своего номера минимальный из номеров склеиваемых вершин. Требуется за наименьшее число операций склейки добиться того, чтобы в графе из любой вершины можно было попасть в любую другую.
\textbf{Входные данные} Первая строка входного файла содержит целые числа \textbf{N} и \textbf{M} --- количество вершин и дуг в исходном графе (\textbf{1} ≤ \textbf{N} ≤ \textbf{200}). Следующие \textbf{M} строк содержат описания дуг, каждая из которых задается номером начальной и конечной вершины. Граф не содержит петель и кратных ребер. \textbf{Выходные данные} В выходной файл выведите \textbf{K} --- число операций склейки.
Input example #1
4 4 1 2 4 3 1 3 4 2
Output example #1
2