20294번 - 에어컨 설치

에어컨 사업을 하는 주현이에게, 새롭게 지어지는 뉴욜라 도서관에서 에어컨 설치 문의가 들어왔다. 도서관 측에서는 설계 도면을 주고 적당한 곳에 에어컨을 설치해달라고 요청했다. 오랜만에 떼돈을 벌 기회를 잡은 주현이는 신나는 마음으로 도면을 확인했다.

도서관 측의 남다른 건축학적 이념을 담은 뉴욜라 도서관의 설계 도면은 독특한 구조로 되어 있는데, $3$차원 도면의 정수 좌표에 해당하는 곳에만 방을 만들었고 두 방의 좌표 사이의 거리가 $1$인 방 사이에는 항상 복도 또는 계단이 있다는 점이다. 이때, 방의 부피는 고려하지 않는다.

최대한 에어컨을 많이 팔고 싶었던 주현이는 모든 방에 에어컨을 설치해야 한다고 강력하게 말하고 싶었지만, 아쉽게도 에어컨은 인접한 방까지 냉방이 가능한 에어컨 뿐이었다. 다시 말해, 에어컨 한 대는 에어컨이 설치된 방을 포함하여, 그 방과 연결된 복도와 계단, 그리고 그 복도와 계단으로 이어져 있는 방까지 냉방이 가능하다.

물론 도서관 관계자들을 속여 모든 방에 에어컨을 설치해도 되겠지만, 바가지를 씌우면 미래의 사업에 차질이 생길 수도 있기 때문에 모든 방과 복도, 계단의 냉방이 가능한 최소 수의 에어컨만을 팔고자 한다.

주현이는 도서관에 몇 대의 에어컨을 팔 수 있을까?

첫째 줄에 도서관의 방의 개수 $N$이 주어진다. ($1 \leq N \leq 1\ 500$)

둘째 줄부터 $N$개 줄에 각 방의 정수 좌표 $x_i, y_i, z_i$가 주어진다. ($-200 \leq x_i, y_i, z_i \leq 200$, $( x_i, y_i, z_i ) \neq ( x_j, y_j, z_j )$ if $i \neq j$)

주현이가 팔 수 있는 에어컨의 최소 수를 출력한다.