안전 지대

좀비 바이러스로 인해 지구는 멸망했고, $N$개의 군부대만이 생존하였다. 지구는 좌표공간 위에서 $-10^9 \leq x \leq 10^9, -10^9 \leq y \leq 10^9$를 만족하는 직사각형 영역이다. 군부대는 직사각형 형태의 안전 지대를 관리한다. 구체적으로, $0 \leq i \leq N - 1$에 대해 $i$번째 군부대는 $A[i] \leq x \leq C[i], B[i] \leq y \leq D[i]$를 만족하는 직사각형 영역 내부 및 경계를 안전 지대로서 관리한다.

두 군부대가 관리하는 안전 지대가 모두 포함하는 점이 존재한다면, 두 군부대는 연결된다. 만약 $0 \leq i, j, k \leq N - 1, i \neq j, j \neq k, k \neq i$에 대하여 $i$번 군부대와 $j$번 군부대가 연결되어 있고, $j$번 군부대와 $k$번 군부대가 연결되어 있다면 $i$번과 $k$번 군부대 또한 연결된다. 어떤 군부대의 집합이 모두 서로 연결되어 있으며, 집합에 속하지 않은 모든 군부대와 연결되어 있지 않다면, 이러한 집합을 연합이라고 한다.

당신은 화성 기지의 공무원으로, 지구에 보급선을 파견해야 한다. 효율적인 보급을 위해 지구에서 각 군부대가 관리하는 안전 지대 정보를 이용하여 모든 연합 정보를 알아내는 함수를 작성하라.

• $1 \le N \le 500\,000$
• $-10^{9} \le A[i], B[i], C[i], D[i] \le 10^{9}$ (모든 $0 \le i \le N-1$)
• $A[i] \le C[i]$, $B[i] \le D[i]$