Japan Alumni Group Summer Camp 2013 Warming Up
I - Topology
Time limit時間制限 : 1.5sec / Memory limitメモリ制限 : 96MB
KM discovered that the number of holes is very important for some geometrical problems. He wants to calculate the number of holes of various figures. To simplify this problem, he assumes that the figures are composed of some unit squares whose vertices are on lattice points.
He can calculate it when the number of the squares is small. He can't calculate it by hand when the number is large, so he asks you, the friend of him and the excellent programmer, to solve this problem by computers.
A hole is a bounded connected component when all squares are removed. When two components share some edges, they are considered connected.
Figure 1: Holes
The first line of the input file contains N (1 \leq N \leq 10^5), which is the number of squares.
Each of the following N lines describes a square by specifying integers X and Y (|X|, |Y| \leq 10^9) separated by single blank characters. X and Y are coordinates of the lower left corner.
You can assume that any two coordinates are different.
Output the number of the holes that the figure has.
The First KMCMonthly Contest