Meeting
Tom and Jerry have decided to have a truce, and would like to sit down together for a nice chat. Their house is in the form of a graph, of N vertices labelled 0 to N-1, and M edges between them. Being restless however, at each point of time, they move from one node to an adjacent node, possibly revisiting earlier nodes.
Count the number of node-pairs (T, J) such that, when Tom starts from T, and Jerry starts from J, it is possible for them to both reach some node simultaneously.
REMEMBER: at each point of time they move from node to node, they do not meet across an edge, and are allowed to revisit a previous node.
Input Format:
The first line consists of integers N and M
The next M lines consist of integers u v, denoting an edge between u and v.
Output Format:
Output a single line: the number of pairs (T, J) for which with Tom starting from T and Jerry starting from J, they can reach the same node at the same point of time.
Sample Input 1:
2 1 0 1
Sample Output 1:
2
Sample Input 2:
4 3 0 1 1 2 2 0
Sample Output 2:
10
Explanation:
First sample case, the options are (0, 0) and (1, 1). Note that (1, 0) and (0, 1) will always have Tom and Jerry oscillating, but never meeting.
Second sample case, the options are (3, 3) along with all (x, y) with 0<=x,y<=2.
Time Limit:
4s
Memory Limit:
128 MB