|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #23Ended |
D - Macetas
Languages: C, C++, Java, JavaScript, Haskell, Tiger, Python, Pascal, C#
Time & Memory limits: (details)
A un chico muy travieso le gusta destruir las macetas de flores en el jardín de su mamá. Su mamá tiene $n$ macetas colocadas en fila y en cada una hay escritos tres enteros. Cuando el chico destruye una de las macetas, todas las ubicadas a su derecha y que comparten al menos un número son destruidas al instante. Sin embargo esta regla es aplicada recursivamente, por lo que destruir una maceta puede traer consigo que se destruyan muchas macetas simultáneamente. El malvado chico quiere saber cuál es la menor cantidad de macetas que necesita destruir para acabar con todas en el jardín de su mamá. Tu tarea es ayudarlo.
Input
La primera línea contine un entero $n$ $(1 \leq n \leq 300000)$ — la cantidad de macetas en el jardín. En cada una de las siguientes $n$ líneas aparecen tres enteros $a_i$, $b_i$, $c_i$ — los número escritos en la i-ésima maceta $(1 \leq a_i,b_i,c_i \leq 1000000)$.
Output
En la única línea de la salida imprima la respuesta al problema.
Sample test(s)
Input
3
1 2 3
2 3 4
4 5 6
Output
1
Input
5
3 4 1
2 5 6
7 2 8
2 1 9
11 10 9
Output
2