Задачи
Ориентация графа
Ориентация графа
Задан неориентированный граф с \textbf{N} вершинами, пронумерованными целыми числами от \textbf{1} до \textbf{N}. Напишите программу, которая последовательно решает следующие задачи:
а) выясняет количество компонент связности графа;
б) находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности;
в) определяет, можно ли ориентировать все ребра графа таким образом, чтобы получившийся граф оказался сильно связным (ориентированный граф называется сильно связным, если из любой его вершины можно пройти в любую другую, двигаясь по ребрам вдоль стрелок);
г) ориентирует максимальное количество ребер, чтобы получившийся граф оказался сильно связным;
д) определяет минимальное количество ребер, которые следует добавить в граф, чтобы ответ на пункт в) был утвердительным.
\InputFile
Во входном файле записано целое число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}) и список ребер графа, заданных номерами концевых вершин.
\OutputFile
Ваша программа должна вывести в выходной файл последовательно ответы на пункты a)-д) в следующем формате:
\begin{itemize}
\item в первой строке запишите ответ на пункт а);
\item во второй строке запишите количество ребер из ответа на пункт б), а в последующих строках выдайте сами эти ребра;
\item в следующую строку выведите сообщение "\textbf{NOT POSSIBLE}", если требуемым в пункте в) способом ориентировать граф невозможно, иначе выведите сообщение "\textbf{POSSIBLE}";
\item далее выведите максимальное количество ребер графа, которые можно ориентировать (пункт г); в последующие строки выведите список этих ребер;
\item в качестве ответа на пункт д) выведите количество ребер, которые следует добавить в исходный граф, а далее выведите сами эти ребра.
\end{itemize}
Ребра задаются указанием номеров своих концевых вершин, а при выводе ответа на пункт г) должна быть указана их ориентация (вначале выводится номер начальной вершины, затем -- номер конечной). Если ответ на пункт а) отличен от единицы, то пункты в) и г) решать не следует и ответы на них не выводятся.
Баллы начисляются лишь в том случае, если программа правильным образом вывела ответы на все вопросы.
Входные данные #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