Descripción

Llegó la entrega de los premios Kariels (los premios a los mejores problemas de Karel del año). Este año, Karel es el encargado de la logística.

Como en cualquier gran entrega de premios, debe existir una alfombra roja por la que entrarán los invitados de honor. Pero en el mundo de Karel nada es tan sencillo y poner la alfombra roja tiene algunas complicaciones. El pasillo de entrada al auditorio no es, como esperarías, un pasillo simple, es un pasillo de ancho uno que puede tener varias bifurcaciones. La siguiente figura muestra un ejemplo posible de pasillo:

En la figura se ve a Karel en un extremo del pasillo, justo en la entrada del auditorio y puedes observar como el pasillo contiene múltiples bifurcaciones.

Karel debe alfombrar todo el pasillo. Para hacerlo, Karel cuenta con sólo un rollo de alfombra roja. La alfombra que usará Karel puede usarse en pasillos rectos o incluso dar vueltas en cualquier dirección, sin embargo no puede dividirse. Por lo tanto Karel se verá obligado a cortar su rollo en varios pedazos para poder alfombrar el pasillo. (Te recomendamos revisar los ejemplos para que esto te quede más claro)

A Karel no le gusta mucho la idea de cortar su alfombra, por lo que pide tu ayuda para que le digas ¿cuál es el menor número de trozos que tiene que cortar para poder alfombrar todo el pasillo?

Problema

Escribe un programa que le permita a Karel determinar el mínimo número de trozos en que debe cortar su rollo y deje un montón de zumbadores con ese número en su posición de inicio.

Ejemplo

Explicación

Para alfombrar el pasillo completo Karel debe cortar el rollo de alfombra en al menos 6 trozos. Observa la siguiente figura:

Los colores no tienen ningún significado en especial, se usan únicamente para diferenciar de forma más sencilla. Como fueron necesarios 6 trozos, Karel deberá dejar un montón con 6 zumbadores en su posición de inicio.

Consideraciones

• Karel siempre inicia en el extremo del pasillo que está junto a la entrada del auditorio viendo hacia el pasillo. Karel no tiene pared a sus espaldas.
• Karel lleva infinitos zumbadores en la mochila.
• Todas las bifurcaciones del pasillo serán siempre de ancho 1.
• No hay ningún zumbador en el mundo de Karel.
• No importa la posición ni la orientación final de Karel.
• Para obatener los puntos debes dejar un montón de zumbadores en la posición inicial de Karel con el número mínimo de trozos en que tienes que cortar el rollo de alfombra.

Subtareas

• (15 puntos): Se asegura que el resultado óptimo siempre será 1 ó 2.
• (25 puntos): Se asegura que hay una forma óptima de alfombrar el mundo usando sólo trozos que sean rectos, es decir, ningún trozo dará vuelta.
• (60 puntos): Sin restricciones adicionales.