Дан ориентированный граф, вершины в котором занумерованы числами от 1 до N
. В нем разрешается выполнять операцию склейки двух вершин, которая заключается в том, что из графа удаляются две вершины и добавляется одна новая вершина, в которую идут дуги из тех вершин, из которых были дуги хотя бы в одну из удаленных вершин, и из которой идут дуги во все вершины, куда шли дуги хотя бы из одной из удаленных вершин. Новая вершина получает в качестве своего номера минимальный из номеров склеиваемых вершин.Требуется за наименьшее число операций склейки добиться того, чтобы в графе из любой вершины можно было попасть в любую другую.
Первая строка входного файла содержит целые числа N
и M
— количество вершин и дуг в исходном графе (1 ≤ N ≤ 200
). Следующие M
строк содержат описания дуг, каждая из которых задается номером начальной и конечной вершины. Граф не содержит петель и кратных ребер.
В выходной файл выведите K
— число операций склейки.