Graph Orientation#2800
An undirected graph with vertices, numbered from to , is given. Write a program that sequentially solves the following tasks:
[a)] Determine the number of connected components of the graph.
[b)] Find and output all edges whose removal increases the number of connected components in the graph.
[c)] Determine whether it is possible to orient all edges of the graph so that the resulting directed graph is strongly connected (a directed graph is strongly connected if it is possible to reach any vertex from any other by following the direction of the edges).
[d)] Orient the maximum number of edges so that the resulting directed graph is strongly connected.
[e)] Find the minimum number of edges that should be added to the graph so that the answer to part c) is positive.
The input file contains an integer (1 \leq N \leq 100) and a list of the edges of the graph, given by their terminal vertex numbers.
Your program should output the answers to points a)–e) in the following format:
On the first line, output the answer to part a).
On the second line, output the number of edges from part b), followed by the list of these edges on the next lines.
On the next line, output "NOT POSSIBLE" if it is not possible to orient the graph as described in part c); otherwise, output "POSSIBLE".
Then, output the number of graph edges that can be oriented as in part d); on the following lines, print these edges with their orientation (first the starting vertex, then the ending vertex).
For part e), output the number of edges that should be added to the original graph, followed by the list of these edges.
Edges are specified by the numbers of their terminal vertices, and for the answer to part d), their orientation must be shown (first the starting vertex, then the ending vertex).
If the answer to part a) is not one, you should not solve or output the answers for parts c) and d).
Points are awarded only if the program correctly outputs the answers to all the tasks.
Example 1