시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 77 20 19 39.583%

문제

상근이는 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)

출력

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

예제 입력 1

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

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjMwODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NTRcdWJkODQgXHViZDgwXHVjMjE4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgSzUxMiBcdWI0YTRcdWNhYmRcdWM1ZDAgXHVkNjU0XHViZDg0IE5cdWFjMWNcdWI5N2MgXHViMTkzXHVjNTU4XHViMmU0LiBcdWQwZGNcdWM2NDRcdWM3NzRcdWIyOTQgXHVjNzc0IFx1ZDY1NFx1YmQ4NFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViZDgwXHVjMjE4XHVjNWI0IFx1YmM4NFx1YjlhY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDY1NFx1YmQ4NFx1Yzc0MCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzEzOCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjNGYwXHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGRjXHVjNjQ0XHVjNzc0XHVhYzAwIFx1ZDY1NFx1YmQ4NCBcdWQ1NThcdWIwOThcdWI5N2MgXHVhZTdjXHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1ZDY1NFx1YmQ4NFx1YzVkMCBcdWM0ZjBcdWM1ZWNcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNjQwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNzg0XHVjNzU4XHVjNzU4IFx1ZDY1NFx1YmQ4NFx1YzVkMCBcdWM0ZjBcdWM1ZWNcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1ZDU1OFx1YjA5OFx1Yjc3Y1x1YjNjNCBcdWFjYjlcdWNlNWNcdWIyZTRcdWJhNzQgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1ZDY1NFx1YmQ4NFx1Yzc0MCBcdWFlNjhcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWM1ZjBcdWMxYzRcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNzdjXHVjNWI0XHViMDljXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1ZDBkY1x1YzY0NFx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWJkODQgXHVkNTU4XHViMDk4XHViOWNjIFx1YWU2OFx1YzExYyBcdWJhYThcdWI0ZTAgXHVkNjU0XHViZDg0XHVjNzQ0IFx1YWU3MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NThcdWM2NzhcdWI4NWMgXHVhYzhjXHVjNzNjXHViOTc4IFx1YzU0NFx1Yzc3NFx1Yzc3OCBcdWQwZGNcdWM2NDRcdWM3NzRcdWIyOTQgXHViNDE4XHViM2M0XHViODVkIFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM3NTggXHVkNjU0XHViZDg0XHVjNzQ0IFx1YzljMVx1YzgxMSBcdWFlNjhcdWMxMWMgXHViYWE4XHViNGUwIFx1ZDY1NFx1YmQ4NFx1Yzc0NCBcdWFlNjhcdWM5YzBcdWFjOGMgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQwZGNcdWM2NDRcdWM3NzRcdWFjMDAgXHVjOWMxXHVjODExIFx1YWU2OFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWQ2NTRcdWJkODRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wb3Rwb3QucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTM3cHg7IHdpZHRoOjM0MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgMlx1YmM4OCBcdWQ2NTRcdWJkODRcdWM3NDQgXHVhZTZjXHViMmU0XHViYTc0LCAzXHViYzg4XHVhY2ZjIDRcdWJjODggXHVkNjU0XHViZDg0XHVjNzQwIFx1YzIyYlx1Yzc5MCAyXHVhYzAwIFx1YWNiOVx1Y2U1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVkNjU0XHViZDg0XHVjNzc0IFx1YWU2OFx1YzljMFx1YmE3MCwgXHVjMjJiXHVjNzkwIDlcdWFjMDAgXHVhY2I5XHVjZTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWQ2NTRcdWJkODQgNVx1YWMwMCBcdWFlNjhcdWM5YzBcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM3NzRcdWM4MWMgXHViMGE4XHVjNzQwIFx1ZDY1NFx1YmQ4NFx1Yzc0MCAxXHViYzg4XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgMVx1YmM4OFx1YjljYyBcdWFlNjhcdWJhNzQgXHViYWE4XHViNGUwIFx1ZDY1NFx1YmQ4NFx1Yzc0NCBcdWFlNzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkMGRjXHVjNjQ0XHVjNzc0XHViMjk0IFx1ZDY1NFx1YmQ4NCBcdWI0NTAgXHVhYzFjXHViOTdjIFx1YzljMVx1YzgxMSBcdWFlNjhcdWMxMWMgXHViYWE4XHViNGUwIFx1ZDY1NFx1YmQ4NFx1Yzc0NCBcdWFlNzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNjU0XHViZDg0XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQ2NTRcdWJkODRcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTAgXHVjMTM4IFx1YWMxYyBBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4sIEM8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4sIEM8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMGRjXHVjNjQ0XHVjNzc0XHVhYzAwIFx1YzljMVx1YzgxMSBcdWFlNjhcdWM1N2NcdWQ1NThcdWIyOTQgXHVkNjU0XHViZDg0IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFWEFNIiwiZGVzY3JpcHRpb24iOiI8cD5NYXJ0aW4gaXMgYSBiZWFzdGx5IGtpZCwgd2hvIGxpa2VzIGRlc3Ryb3lpbmcgaGlzIG1vdGhlciYjMzk7cyBmbG93ZXIgcG90cy4gSGlzIG1vdGhlciBvd25zIE4gZmxvd2VyIHBvdHMgc2V0IHVwIGluIGEgbGluZSBhbmQgZWFjaCBwb3QgaGFzIHRocmVlIGludGVnZXJzIHdyaXR0ZW4gb24gaXQuIFdoZW4gTWFydGluIGNyYXNoZXMgb25lIG9mIHRob3NlIHBvdHMsIGV2ZXJ5IHBvdCByaWdodCBvZiB0aGF0IHBvdCBhbmQgc2hhcmVzIGF0IGxlYXN0IG9uIG51bWJlciB3aXRoIGl0IGFsc28gZmFsbHMuIE1vcmVvdmVyLCB0aGlzIHJ1bGUgaXMgYXBwbGllZCByZWN1cnNpdmVseSwgdGh1cyBjYW4gcmVzdWx0IGluIGNyYXNoaW5nIG9mIHdob2xlIGxvdHRhIHBvdHMgZnJvbSBqdXN0IG9uZSBkaXJlY3QgcG90IGNyYXNoIGZyb20gTWFydGluLiBCZWFzdGx5IGtpZHMgYXJlIGtub3duIHRvIGJlIGxhenkgYW5kIHNvIGlzIE1hcnRpbiwgYW5kIGhlIHdhbnRzIHRvIGtub3cgdGhlIG1pbmltYWwgbnVtYmVyIG9mIHBvdHMgaGUgaGFzIHRvIGNyYXNoIGRpcmVjdGx5IHNvIHRoYXQgYWxsIHBvdHMgZW5kIHVwIGRlc3Ryb3llZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wb3Rwb3QucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTM3cHg7IHdpZHRoOjM0MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk9uIHRoZSBwaWN0dXJlIGFib3ZlIHRoZSBzZWNvbmQgc2FtcGxlIGlzIHNob3duLiBJZiBEb21hZ29qIGNyYXNoZXMgcG90IDIsIGl0IHdpbGwgYWxzbyBjcmFzaCBwb3QgMyBhbmQgcG90IDQgYmVjYXVzZSBvZiBudW1iZXIgMiBhbmQgYWRkaXRpb25hbHkgcG90IDUgYmVjYXVzZSBvZiBudW1iZXIgOSAoZm91bmQgb24gcG90IDQpLiBIZSBuZWVkcyB0byBjcmFzaCBwb3QgMSwgd2hpY2ggd2lsbCBjYXVzZSB0aGUgY3Jhc2hpbmcgb2YgcG90IDMuIFRoaXMgYW1vdW50cyB0byB0d28gZGlyZWN0IGNyYXNoZXMgZnJvbSBNYXJ0aW4gYW5kIGlzIHRoZSBzb2x1dGlvbiB0byB0aGUgc2FtcGxlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBjb250YWlucyBvbmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMCAwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0aHJlZSBpbnRlZ2VyJm5ic3A7QTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+LCBDPHN1Yj5pPFwvc3ViPiAoMSAmbGU7Jm5ic3A7QTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+LCBDPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCksIHRocmVlIG51bWJlcnMgd3JpdHRlbiBvbiB0aGUgaS10aCBwb3QgZnJvbSB0aGUgbGVmdC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSB3cml0ZSB0aGUgbWluaW1hbCBudW1iZXIgb2YgcG90cyBNYXJ0aW4gaGFzIHRvIGNyYXNoIGhpbXNlbGYgdG8gY3Jhc2ggYWxsIHRoZSBwb3RzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==