Задача №3360. Авиалинии
В Берляндии скоро появятся свои авиалинии. Комитет по разработке берляндских авиалиний уже предложил свой вариант соединения городов авиарейсами. Каждый авиарейс задается парой различных городов. Рейсы односторонние. Президенту понравился план, однако он показался ему чересчур неэкономным. Требуется разработать новый план, который содержит наименьшее количество авиарейсов и удовлетворяет условию: если из города a можно было попасть в город b (возможно, с пересадками) согласно первоначальному плану, то и в новом плане это должно быть возможным. Если же это было сделать невозможно, то и согласно новому плану это не должно быть возможным. Очевидно, что из любого города можно попасть в него самого.
В первой строке входного файла записаны целые числа \(N\) и \(M\) (\(1 \leq N \leq 1000\), \(0 \leq M \leq 10000\)), где \(N\) – количество городов в стране, а \(M\) – количество авиарейсов в первоначальном плане. Города нумеруются от 1 до \(N\). Далее записано \(M\) пар различных чисел \(a_i\), \(b_i\) обозначающих наличие рейса из \(a_i\) в \(b_i\) в первоначальном плане (\(1 \leq a_i \leq N\), \(1 \leq b_i \leq N\)). Пары разделяются пробелами или переводами строк. Между парой городов может быть более одного авиарейса.
В первую строку выходного файла выведите количество рейсов в новом плане. Далее выведите авиарейсы в формате, аналогичном формату входных данных. Пары разделяйте пробелами или переводами строк. Пары выводите в любом порядке. Если существует несколько решений, выведите любое.
Тесты при \(N \le 20\), \(M \le 40\) оцениваются в 40 баллов и только при прохождении всех тестов группы.
Остальные тесты оцениваются независимо, но только при прохождении всех тестов первой группы.
4 5 1 2 2 3 2 1 3 2 2 4
4 1 3 3 2 2 1 2 4