24282번 - Connect 서브태스크다국어

You are given a graph with n vertices and m undirected edges. The vertices are numbered from 1 to n. We number the edges in the order of their appearance in the input, starting with 1. Let for each pair of numbers of edges (i, j) for which 1 ≤ i ≤ j ≤ m, create a new graph with edges that are the edges of the original graph with numbers from i to j inclusive and for the vertices of the new graph we take all vertices of the original graph. Write program connect that finds how many of these newly created graphs are connected.

The first line of the standard input contains the values of n and m. It follows m lines in the input, each containing two integers: u and v, specifying the vertices of the corresponding edge in the original graph.

Your program should print on the standard output one integer equal to the count of newly created connected graphs.

• 2 ≤ n ≤ 50 000
• 1 ≤ m ≤ 200 000
• 1 ≤ u ≤ n
• 1 ≤ v ≤ n
• The graph may contain multi-edges and loops.

The pairs of edges (i, j) for which the corresponding new graph is connected are (1, 3), (1,4) and (2,4). More precisely:

• (1,3) – this includes edges with numbers 1, 2 and 3;
• (1,4) – this includes edges with numbers 1, 2, 3 and 4;
• (2,4) – this includes edges with numbers 2, 3 and 4.