Cycle Counting with DSU

You are given a graph with n locations and m paths. Each path connects two locations and is added sequentially. Your task is to count the number of cycles (loops) formed after each path is added. A cycle is formed when a newly added edge connects two vertices that are already connected via previously added paths.

More formally, let the graph initially have n nodes and no edges. For each of the m edges given in order, add the edge to the graph. Define loops[i] as the number of cycles formed up to the i-th edge. Two nodes are considered connected if there exists a path between them. When adding an edge that connects two already connected nodes, increment the cycle counter by 1.

The DSU (Disjoint Set Union) data structure is recommended for efficiently tracking connectivity. In DSU, the find operation locates the representative of a node's connected component. The union operation merges two components if they are distinct. Note that if the two nodes of the edge already share the same representative, a cycle is formed.

Note: All arithmetic should be performed modulo \(10^9+7\) (i.e., \(1000000007\)).

inputFormat

The first line contains two space-separated integers: n (the number of locations) and m (the number of paths).

Each of the following m lines contains two space-separated integers a and b indicating that there is a path between location a and location b. The locations are numbered from 1 to n.

outputFormat

Output a single line containing m space-separated integers. The i-th integer should be the total number of cycles (modulo \(10^9+7\)) after adding the first i edges.

4 4
1 2
2 3
3 4
4 2

0 0 0 1