화분 부수기

상근이는 K512 뒤쪽에 화분 N개를 한 줄로 놓았다. 태완이는 이 화분을 모두 부수려고 한다. 각 화분에는 세 개의 정수가 쓰여 있다.

태완이가 어떤 화분 하나를 직접 깨면, 그 화분에 쓰인 숫자 중 하나라도 같은 숫자가 적힌 오른쪽 화분들도 함께 깨진다. 이렇게 새로 깨진 화분들에 대해서도 같은 일이 다시 일어나므로, 깨지는 과정은 연쇄적으로 이어질 수 있다. 따라서 화분 하나를 직접 깨는 것만으로도 오른쪽의 여러 화분이 함께 깨질 수 있다.

태완이는 되도록 적은 수의 화분만 직접 깨서 모든 화분이 깨지게 만들고 싶다. 태완이가 직접 깨야 하는 화분 개수의 최솟값을 구하시오.

위 그림에서 2번 화분을 깨면 숫자 2가 겹치기 때문에 3번과 4번 화분도 깨진다. 이어서 숫자 9가 겹치기 때문에 5번 화분도 깨진다. 이제 1번 화분만 남으므로, 1번 화분도 직접 깨면 모든 화분을 깰 수 있다. 이 경우 태완이는 화분 두 개를 직접 깨면 된다.

첫째 줄에 화분의 개수 N이 주어진다 (1 <= N <= 300,000).

다음 N개 줄에는 각 화분에 쓰여 있는 세 정수 Ai, Bi, Ci가 화분이 놓인 순서대로 주어진다 (1 <= Ai, Bi, Ci <= 1,000,000).

태완이가 직접 깨야 하는 화분 개수의 최솟값을 출력한다.