화분 부수기
시간 제한1초메모리 제한256 MB
숫자 3개씩을 가진 화분들이 번호를 공유하면 뒤쪽 화분이 연쇄적으로 깨질 때, 모든 화분을 깨뜨리기 위해 직접 깨야 하는 최소 화분 수를 구합니다.
문제
상근이는 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).
출력
태완이가 직접 깨야 하는 화분 개수의 최솟값을 출력한다.