삼각 분할

계산기하학에서 삼각 분할(triangulation) 이란 다음 두 조건을 만족하는 삼각형들의 집합이다.

• 각 삼각형의 세 꼭짓점은 모두 주어진 다각형의 꼭짓점이다.
• 서로 다른 두 삼각형은 내부가 겹치지 않으며, 모든 삼각형의 합집합은 다각형 전체와 같다.

볼록 다각형은 모든 내각이 180도 미만이고 변이 3개 이상인 다각형이다. 볼록 다각형을 두 개의 볼록 다각형으로 나누는 직선을 그 다각형의 절단선이라고 한다.

삼각 분할된 볼록 다각형이 주어지고, 각 삼각형의 내부는 색 $C_i$로 칠해져 있다. 색이 같은 두 점이 서로 다른 조각에 놓이는 일이 절대 없도록 하면서 절단선을 최대한 많이 그으려고 한다. 이때 그을 수 있는 절단선은 최대 몇 개인가?

절단선이 삼각형의 내부를 지나면 그 삼각형의 같은 색 두 점이 서로 다른 조각으로 갈라지므로, 각 절단선은 삼각 분할의 내부 대각선 중 정확히 하나와 일치해야 한다.

첫째 줄에 다각형의 꼭짓점 수 $n$이 주어진다. ($3 \le n \le 100{,}000$)

다음 $n-2$개의 줄에 각 삼각형의 정보가 네 정수 $a\ b\ c\ d$로 주어진다. 이는 그 삼각형의 세 꼭짓점이 다각형의 꼭짓점 $a$, $b$, $c$이고 내부가 색 $d$로 칠해져 있음을 뜻한다. ($1 \le a, b, c, d \le n$)

주어지는 입력은 항상 문제의 조건을 만족하는 올바른 삼각 분할이다.

다각형에 그을 수 있는 절단선의 최대 개수를 한 줄에 출력한다.