World War in Jupiter

Idea:
We expected some more correct submissions for this problem as the problem was actually not that much difficult.
What we were actually asked here is how many triplets (P,U,V) are there such that there is no way to reach V from P without visiting U first. This is where the articulation point idea comes from.

Please check this links if you are not familiar with it:
http://www.shafaetsplanet.com/planetcoding/?p=2504
http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

For any triplet (P,U,V), to be a valid one U must be an articulation point here. Otherwise there will always be at least one way to reach V from P without visiting U.

Now try to visualize one more important thing here. For each of the articulation point U, there must be some component in the graph which will get disconnected with each other if we remove U from this graph.
Let’s S1, S2, S3 … Sk be those components in the graph for any particular articulation point U.
Now for each of the node P from Si, we can take any other node V from Sj (i != j) to make a valid triplet (P,U,V). Because there will be no way to reach V from P if we don’t visit U.
So we can iterate through each of the articulation point and update our result this way. Which can be handled using just DFS. Please make sure to handle the case when there is more than one component in the graph.

Complexity: O(N+M).

Judge Solution: http://ideone.com/SGAlwv

Alternate Writer: Mohammad Abdullah Matin Khan