시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 26 8 7 35.000%

문제

상근이는 K512 뒤쪽에 화분 N개를 놓았다. 태완이는 이 화분을 모두 부수어 버리려고 한다. 화분은 한 줄로 놓여져 있으며, 세 정수가 쓰여져 있다.

태완이가 화분 하나를 깼을 때, 그 화분에 써 있는 숫자와 오른쪽 화분에 써 있는 숫자가 적어도 하나가 겹친다면 오른쪽 화분도 깨진다. 이것은 연쇄적으로 일어난다. 따라서, 태완이는 화분 하나만 깨서 모든 화분을 깰 수 있다.

의외로 게으른 아이인 태완이는 되도록 적은 수의 화분을 직접 깨서 모든 화분을 깨지게 만드려고 한다. 이 때, 태완이가 직접 깨야하는 화분의 최소 개수를 구하는 프로그램을 작성하시오.

위의 그림에서 2번 화분을 깬다면, 3번과 4번 화분은 숫자 2가 겹치기 때문에 화분이 깨지며, 숫자 9가 겹치기 때문에 화분 5가 깨지게 된다. 이제 남은 화분은 1번이기 때문에, 1번만 깨면 모든 화분을 깰 수 있다. 태완이는 화분 두 개를 직접 깨서 모든 화분을 깰 수 있다.

입력

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

다음 N개 줄에는 각 화분에 써있는 숫자 세 개 Ai, Bi, Ci가 놓여져 있는 순서대로 주어진다. (1 ≤ Ai, Bi, Ci ≤ 1,000,000)

출력

첫째 줄에 태완이가 직접 깨야하는 화분 개수의 최소값을 출력한다.

예제 입력

5
3 4 1
2 5 6
7 2 8
2 1 9
11 10 9

예제 출력

2

힌트