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

Ориентация графа

Ориентация графа

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

Задан неориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Напишите программу, которая последовательно решает следующие задачи:

а) выясняет количество компонент связности графа;

б) находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности;

в) определяет, можно ли ориентировать все ребра графа таким образом, чтобы получившийся граф оказался сильно связным (ориентированный граф называется сильно связным, если из любой его вершины можно пройти в любую другую, двигаясь по ребрам вдоль стрелок);

г) ориентирует максимальное количество ребер, чтобы получившийся граф оказался сильно связным;

д) определяет минимальное количество ребер, которые следует добавить в граф, чтобы ответ на пункт в) был утвердительным.

Вхідні дані

Во входном файле записано целое число N (1N100) и список ребер графа, заданных номерами концевых вершин.

Вихідні дані

Ваша программа должна вывести в выходной файл последовательно ответы на пункты a)-д) в следующем формате:

  • в первой строке запишите ответ на пункт а);

  • во второй строке запишите количество ребер из ответа на пункт б), а в последующих строках выдайте сами эти ребра;

  • в следующую строку выведите сообщение "NOT POSSIBLE", если требуемым в пункте в) способом ориентировать граф невозможно, иначе выведите сообщение "POSSIBLE";

  • далее выведите максимальное количество ребер графа, которые можно ориентировать (пункт г); в последующие строки выведите список этих ребер;

  • в качестве ответа на пункт д) выведите количество ребер, которые следует добавить в исходный граф, а далее выведите сами эти ребра.

Ребра задаются указанием номеров своих концевых вершин, а при выводе ответа на пункт г) должна быть указана их ориентация (вначале выводится номер начальной вершины, затем – номер конечной). Если ответ на пункт а) отличен от единицы, то пункты в) и г) решать не следует и ответы на них не выводятся.

Баллы начисляются лишь в том случае, если программа правильным образом вывела ответы на все вопросы.

Приклад

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