Road Construction and Connected Components

You are given a city with n intersections and no roads initially. Roads will be constructed one by one. Each road connects two intersections. After each road construction, your task is to determine the number of connected components (i.e. groups of intersections that are connected directly or indirectly by roads) in the city.

Formally, you are given an integer \(n\) representing the number of intersections and an integer \(m\) representing the number of roads. Then, \(m\) lines follow, each containing two integers \(u\) and \(v\) (1-indexed) representing a road connecting intersections \(u\) and \(v\). Initially, the graph has \(n\) connected components. For each road addition, if the two intersections are in different connected components, they are merged, reducing the total number of connected components. Output the number of connected components after each road construction.

Note: Use Union-Find (Disjoint Set Union) with path compression and union by rank for an efficient solution.

inputFormat

The first line contains two integers \(n\) and \(m\): the number of intersections and the number of roads, respectively.

The next \(m\) lines each contain two integers \(u\) and \(v\), indicating that a road is constructed connecting intersections \(u\) and \(v\).

outputFormat

Output \(m\) lines. The \(i\)-th line should contain a single integer representing the number of connected components after adding the \(i\)-th road.

## sample

5 3
1 2
3 4
2 4

4
3
2

</p>