Score : 800 points
Takahashi has received an undirected graph with N vertices, numbered 1, 2, ..., N. The edges in this graph are represented by (u_i, v_i). There are no self-loops and multiple edges in this graph.
Based on this graph, Takahashi is now constructing a new graph with N^2 vertices, where each vertex is labeled with a pair of integers (a, b) (1 \leq a \leq N, 1 \leq b \leq N). The edges in this new graph are generated by the following rule:
How many connected components are there in this new graph?
The input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 : u_M v_M
Print the number of the connected components in the graph constructed by Takahashi.
3 1 1 2
7
The graph constructed by Takahashi is as follows.
7 5 1 2 3 4 3 5 4 5 2 6
18