Орієнтація графа#2800
Дано неорієнтований граф з вершинами, пронумерованими від до . Напишіть програму, яка послідовно розв'язує такі задачі:
[a)] Визначити кількість зв'язних компонентів графа.
[b)] Знайти й вивести всі ребра, видалення яких збільшує кількість зв'язних компонентів графа.
[c)] Визначити, чи можна так орієнтувати всі ребра графа, щоб отриманий орієнтований граф став сильно зв'язним (орієнтований граф є сильно зв'язним, якщо з будь-якої вершини можна досягти будь-якої іншої у напрямку стрілок).
[d)] Орієнтувати максимально можливу кількість ребер так, щоб отриманий орієнтований граф був сильно зв'язним.
[e)] Визначити мінімальну кількість ребер, які потрібно додати до графа, щоб відповідь на частину c) була позитивною.
У вхідному файлі задано ціле число (1 \leq N \leq 100) і список ребер графа, поданих номерами кінцевих вершин.
Ваша програма має вивести відповіді на пункти a)–e) у такому форматі:
У першому рядку — відповідь на пункт a).
У другому рядку — кількість ребер з пункту b), а на наступних рядках — список цих ребер.
У наступному рядку вивести "NOT POSSIBLE", якщо неможливо орієнтувати граф, як у пункті c); інакше — "POSSIBLE".
Потім — кількість ребер графа, які можна орієнтувати згідно з пунктом d); на наступних рядках ці ребра з орієнтацією (спочатку початкова, потім кінцева вершина).
Для пункту e) вивести кількість ребер, які потрібно додати до початкового графа, а далі — список цих ребер.
Ребра задаються номерами своїх кінцевих вершин, а у відповіді на пункт d) слід вказати їх орієнтацію (спочатку початкова, потім кінцева вершина).
Якщо відповідь на пункт a) не дорівнює одиниці, завдання пунктів c) та d) не потрібно розв'язувати й виводити.
Бали нараховуються лише у разі, якщо програма правильно виведе відповіді на всі задачі.
Приклад 1