Pintando poliedros P86514

Pedro tiene un poliedro convexo de caras triangulares y quiere pintar sus caras sin que dos caras adyacentes tengan el mismo color. Dispuesto a comprar pintura, se pregunta cuál es el menor número de colores necesarios. Tras fracasar buscando la respuesta, su amigo, un turista bielorruso, le dice lo siguiente:

­– “Te daré una pista para que lo puedas pintar. Si pones un vértice en cada cara y unes los vértices que estén en caras adyacentes, obtienes un grafo. Tu problema es equivalente a colorear ese grafo con el menor número de colores. Y por si no te has dado cuenta, por venir de un poliedro, el grafo será siempre cúbico, planar y tres-conexo.”

Pedro sigue sin tener ni idea, así que os ha dejado el problema a vosotros. Recordad que un grafo cúbico es aquel en que todo vértice tiene exactamente tres vecinos, un grafo planar es aquel que se puede pintar en un papel sin que dos aristas se crucen, y un grafo tres-conexo es un grafo conexo al que se le han de quitar por lo menos tres vértices para desconectarlo.

Entrada

La entrada tiene diversos grafos, todos provinientes de un poliedro como se ha descrito anteriormente. Cada grafo empieza con su número de vértices n, seguido de n triplas con los vecinos de cada vértice i. Al final viene la palabra CUENTA o la palabra PINTA. Podéis suponer 4 ≤ n ≤ 20000. Los vértices se numeran desde cero.

Salida

Para cada caso de tipo CUENTA, escribid el mínimo número de colores para pintar el grafo. Para los de tipo PINTA, a continuación escribid los colores de los vértices en orden. Seguid estrictamente el formato de los ejemplos.

Pista

Es conocido que todo grafo planar se puede pintar con cuatro colores o menos.

Puntuación

• Test1:  ‍ Resolver casos de tipo CUENTA donde n ≤ 10.  ‍10 Puntos ‍

• Test2:  ‍ Resolver casos de tipo CUENTA.  ‍30 Puntos ‍

• Test3:  ‍ Resolver casos de tipo PINTA donde n ≤ 10.  ‍10 Puntos ‍

• Test4:  ‍ Resolver casos de tipo PINTA.  ‍50 Puntos ‍