A yard has n tiles placed at distinct integer coordinates (x, y). A crane can salvage a tile only while it shares its row (same x) or its column (same y) with at least one tile still present. Tiles are salvaged one at a time; within any group of tiles connected through shared rows or columns, all but one tile can be salvaged.
Report the maximum number of tiles that can be salvaged. Equivalently, if the tiles form g connected groups (connecting any two tiles that share a row or a column, transitively), the answer is n - g.
Input format
- Line 1: an integer
n, the number of tiles. - Next
nlines: two integersxandy, the coordinates of a tile. All coordinates are distinct.
Output format
A single integer: the maximum number of tiles that can be salvaged.
Constraints
- 1 <= n <= 100000
- 0 <= x, y <= 1000000