You are given a graph of nodes. The graph consists of connected components. Some of the connected components contain a special node and each component contains at most one special node. You are required to maximize the number of edges in the given graph such that it follows these constraints:
If you add an edge between two nodes that belong to the same component in the graph, then the total cost involved is . Whereas, if you connect two nodes that belong to different components, then the cost is equal to the product of the sizes of both the components.
Your task is to maximize the number of new edges in the graph and calculate the minimum cost that will be involved in performing the required task.
Input format
Output format
Print the maximum number of new edges that can be added to the graph and the minimum cost of doing so.
Constraints
The given graph consist of 5 connected components..
1 is the special node in and 4 is the special node in .
There is no special node in .
For :-
We can add 1 edge from 2 to 3, cost = 0 (same component).
For :-
We will add 3 edges from 6 to 5, 6 to 7 and 4 to 7. Now we can't add more edges to this component, cost = 0 (same component).
For the remaining nodes (without special nodes):-
We will first connect and with cost 2 and 2 edges.
Then and with cost 6 and 6 edges. (product of their sizes).
Now we have all the non special nodes completely connected.
We can now connect all the 5 non special nodes to the component with cost 20 and 20 edges.
Hence total cost is 28 and maximum number of edges that can be added are 32.