시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 75 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+XHJcblxyXG48cD5cdWM3NThcdWM2NzhcdWI4NWMgXHVhYzhjXHVjNzNjXHViOTc4IFx1YzU0NFx1Yzc3NFx1Yzc3OCBcdWQwZGNcdWM2NDRcdWM3NzRcdWIyOTQgXHViNDE4XHViM2M0XHViODVkIFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM3NTggXHVkNjU0XHViZDg0XHVjNzQ0IFx1YzljMVx1YzgxMSBcdWFlNjhcdWMxMWMgXHViYWE4XHViNGUwIFx1ZDY1NFx1YmQ4NFx1Yzc0NCBcdWFlNjhcdWM5YzBcdWFjOGMgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVkMGRjXHVjNjQ0XHVjNzc0XHVhYzAwIFx1YzljMVx1YzgxMSBcdWFlNjhcdWM1N2NcdWQ1NThcdWIyOTQgXHVkNjU0XHViZDg0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcG90cG90LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzN3B4OyB3aWR0aDozNDBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIDJcdWJjODggXHVkNjU0XHViZDg0XHVjNzQ0IFx1YWU2Y1x1YjJlNFx1YmE3NCwgM1x1YmM4OFx1YWNmYyA0XHViYzg4IFx1ZDY1NFx1YmQ4NFx1Yzc0MCBcdWMyMmJcdWM3OTAgMlx1YWMwMCBcdWFjYjlcdWNlNThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDY1NFx1YmQ4NFx1Yzc3NCBcdWFlNjhcdWM5YzBcdWJhNzAsIFx1YzIyYlx1Yzc5MCA5XHVhYzAwIFx1YWNiOVx1Y2U1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVkNjU0XHViZDg0IDVcdWFjMDAgXHVhZTY4XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNzc0XHVjODFjIFx1YjBhOFx1Yzc0MCBcdWQ2NTRcdWJkODRcdWM3NDAgMVx1YmM4OFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIDFcdWJjODhcdWI5Y2MgXHVhZTY4XHViYTc0IFx1YmFhOFx1YjRlMCBcdWQ2NTRcdWJkODRcdWM3NDQgXHVhZTcwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDBkY1x1YzY0NFx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWJkODQgXHViNDUwIFx1YWMxY1x1Yjk3YyBcdWM5YzFcdWM4MTEgXHVhZTY4XHVjMTFjIFx1YmFhOFx1YjRlMCBcdWQ2NTRcdWJkODRcdWM3NDQgXHVhZTcwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDY1NFx1YmQ4NFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDMwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkNjU0XHViZDg0XHVjNWQwIFx1YzM2OFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTAgXHVjMTM4IFx1YWMxYyBBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4sIEM8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4sIEM8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMGRjXHVjNjQ0XHVjNzc0XHVhYzAwIFx1YzljMVx1YzgxMSBcdWFlNjhcdWM1N2NcdWQ1NThcdWIyOTQgXHVkNjU0XHViZDg0IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFWEFNIiwiZGVzY3JpcHRpb24iOiI8cD5NYXJ0aW4gaXMgYSBiZWFzdGx5IGtpZCwgd2hvIGxpa2VzIGRlc3Ryb3lpbmcgaGlzIG1vdGhlciYjMzk7cyBmbG93ZXIgcG90cy4gSGlzIG1vdGhlciBvd25zIE4gZmxvd2VyIHBvdHMgc2V0IHVwIGluIGEgbGluZSBhbmQgZWFjaCBwb3QgaGFzIHRocmVlIGludGVnZXJzIHdyaXR0ZW4gb24gaXQuIFdoZW4gTWFydGluIGNyYXNoZXMgb25lIG9mIHRob3NlIHBvdHMsIGV2ZXJ5IHBvdCByaWdodCBvZiB0aGF0IHBvdCBhbmQgc2hhcmVzIGF0IGxlYXN0IG9uIG51bWJlciB3aXRoIGl0IGFsc28gZmFsbHMuIE1vcmVvdmVyLCB0aGlzIHJ1bGUgaXMgYXBwbGllZCByZWN1cnNpdmVseSwgdGh1cyBjYW4gcmVzdWx0IGluIGNyYXNoaW5nIG9mIHdob2xlIGxvdHRhIHBvdHMgZnJvbSBqdXN0IG9uZSBkaXJlY3QgcG90IGNyYXNoIGZyb20gTWFydGluLiBCZWFzdGx5IGtpZHMgYXJlIGtub3duIHRvIGJlIGxhenkgYW5kIHNvIGlzIE1hcnRpbiwgYW5kIGhlIHdhbnRzIHRvIGtub3cgdGhlIG1pbmltYWwgbnVtYmVyIG9mIHBvdHMgaGUgaGFzIHRvIGNyYXNoIGRpcmVjdGx5IHNvIHRoYXQgYWxsIHBvdHMgZW5kIHVwIGRlc3Ryb3llZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wb3Rwb3QucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTM3cHg7IHdpZHRoOjM0MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk9uIHRoZSBwaWN0dXJlIGFib3ZlIHRoZSBzZWNvbmQgc2FtcGxlIGlzIHNob3duLiBJZiBEb21hZ29qIGNyYXNoZXMgcG90IDIsIGl0IHdpbGwgYWxzbyBjcmFzaCBwb3QgMyBhbmQgcG90IDQgYmVjYXVzZSBvZiBudW1iZXIgMiBhbmQgYWRkaXRpb25hbHkgcG90IDUgYmVjYXVzZSBvZiBudW1iZXIgOSAoZm91bmQgb24gcG90IDQpLiBIZSBuZWVkcyB0byBjcmFzaCBwb3QgMSwgd2hpY2ggd2lsbCBjYXVzZSB0aGUgY3Jhc2hpbmcgb2YgcG90IDMuIFRoaXMgYW1vdW50cyB0byB0d28gZGlyZWN0IGNyYXNoZXMgZnJvbSBNYXJ0aW4gYW5kIGlzIHRoZSBzb2x1dGlvbiB0byB0aGUgc2FtcGxlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBjb250YWlucyBvbmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMCAwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0aHJlZSBpbnRlZ2VyJm5ic3A7QTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+LCBDPHN1Yj5pPFwvc3ViPiAoMSAmbGU7Jm5ic3A7QTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+LCBDPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCksIHRocmVlIG51bWJlcnMgd3JpdHRlbiBvbiB0aGUgaS10aCBwb3QgZnJvbSB0aGUgbGVmdC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSB3cml0ZSB0aGUgbWluaW1hbCBudW1iZXIgb2YgcG90cyBNYXJ0aW4gaGFzIHRvIGNyYXNoIGhpbXNlbGYgdG8gY3Jhc2ggYWxsIHRoZSBwb3RzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==