Safe Zone

Due to a zombie virus, the Earth has been destroyed, and only $N$ military units survive. The Earth is a rectangular region in coordinate space that satisfies $-10^9 \leq x \leq 10^9, -10^9 \leq y \leq 10^9$. Each military unit manages a rectangular safe zone. Specifically, for $0 \leq i \leq N - 1$, the $i$-th unit manages the interior and boundary of the rectangle $A[i] \leq x \leq C[i], B[i] \leq y \leq D[i]$ as its safe zone.

Two military units are connected if there is a point contained in both of their safe zones. If $i$ and $j$ are connected, and $j$ and $k$ are connected, for distinct $i, j, k$, then $i$ and $k$ are also connected. A set of military units is called an alliance if every unit in the set is connected to the others, and no unit in the set is connected to any unit outside the set.

• $1 \le N \le 500\,000$
• $-10^{9} \le A[i], B[i], C[i], D[i] \le 10^{9}$ for all $0 \le i \le N-1$
• $A[i] \leq C[i]$, $B[i] \leq D[i]$