Hijos a tope
China es el país más poblado del mundo con más de un quinto de la población mundial. En 1953 empezó a realizarse en el país el primer censo moderno, revelando una población de cerca de 600 millones de habitantes. En los años 60 el gobierno comenzó a promover el retraso en la edad de contraer matrimonio y la planificación familiar. En 1972 se establecieron los primeros límites en el número de hijos por familia, siendo de dos en las ciudades. La política del hijo único se estableció en 1979 con objeto de frenar el crecimiento de la población, cuando esta ya estaba cercana a los 1000 millones de personas. Esta política combinaba el uso de la propaganda, la presión social, el establecimiento de beneficios e incluso penalizaciones económicas. Sin embargo, las minorías étnicas nunca han estado sujetas a dicha política, y en los entornos rurales a las parejas se les ha permitido tener otro hijo si su primogénito fue una niña. En 2015 se puso fin a la política del hijo único permitiendo de nuevo a todas las parejas tener dos hijos.
Un grupo de demógrafos chinos está haciendo un estudio con árboles genealógicos de familias chinas en las que se ha respetado el máximo de dos hijos que se estableció en 1972 y que recientemente se ha recuperado. En cada familia estudian las subfamilias generacionalmente completas, que son aquellas subfamilias en las que todos sus miembros han tenido exactamente dos hijos. Quieren saber cuál es la subfamilia generacionalmente completa con mayor número de generaciones.
Por ejemplo, en el siguiente árbol genealógico se ha resaltado la subfamilia generacionalmente completa con más generaciones, que en este caso son dos.
Entrada
La entrada comienza indicando el número de casos de prueba que vendrán a continuación. Cada caso consiste en una secuencia de números que pueden ser 0, 1 o 2 indicando el número de hijos de los miembros de la familia. Primero aparece el número de hijos de la raíz del árbol genealógico, y si tiene hijos, a continuación figuran las descripciones de las subfamilias de cada uno de sus hijos, que a su vez están descritas de la misma forma.
Los árboles genealógicos nunca contendrán más de 5.000 miembros.
Salida
Para cada árbol genealógico, se escribirá una línea con el número de generaciones de la subfamilia generacionalmente completa con mayor número de generaciones.
Entrada de ejemplo
5 0 2 0 0 1 2 1 0 1 0 2 2 0 1 2 0 0 2 0 0 2 2 2 0 2 1 0 0 2 2 0 0 0 1 2 0 2 0 0
Salida de ejemplo
0 1 1 2 2