Campanadas televisadas
Todas las nocheviejas tenemos conflicto en casa. Nos juntamos toda la familia (abuelos, tíos, primos, parejas, amigos e incluso algún tio abuelo soltero) a cenar deprisa (no hay forma de empezar a una hora razonable con todos los que somos) para dar paso al nuevo año comiendo las 12 uvas al son de las campanadas.
El conflicto llega, precisamente, por las campanadas. Todas las cadenas de televisión luchan, año tras año, por ser el canal más visto de esa nochevieja. Para conseguirlo, ponen delante de la cámara a los presentadores más de moda del año y crean expectación los días previos hablando sobre qué harán o qué ropa llevarán. El resultado es que en mi familia es imposible ponerse de acuerdo sobre qué cadena utilizar para comernos las uvas.
Lo gracioso del asunto es el protocolo que seguimos para decidir qué cadena será la que veamos. Todos nosotros tenemos una cadena preferida y una que no estamos dispuestos a ver. Cuando, antes de sentarnos a cenar, encendemos la televisión, ésta comienza en una cadena arbitraria. Si ninguno de nosotros la odiamos, será la que terminemos viendo. Pero si es una de las que alguno no soporta, éste, disimulando, se levantará haciendo como que va a la cocina a por algo y aprovechará para cambiar de canal poniendo el que prefiere. Si ese no molesta a nadie, se quedará hasta el año siguiente. Si alguien lo aborrece, se levantará y cambiará de canal.
El proceso puede terminar bien si tras unos cuantos cambios se llega a un canal aceptado por todos, o mal si el proceso continua "para siempre", porque llegará el momento de comernos las uvas y seguiremos sin decidir dónde verlas. Todo dependerá del canal que haya puesto al encender la tele... De hecho, hay veces en donde todo dependerá de la suerte, pues hay canales odiados por varios y el resultado podría ser distinto dependiendo de quién sea el que se levante primero para cambiarlo.
Entrada
La entrada esta compuesta por distintos casos de prueba, cada uno ocupando varias líneas.
La primera línea tiene dos números: el número N de canales disponibles (entre 2 y 20.000) y el número M de personas que hay en la familia (entre 1 y 100.000).
A continuación aparecen M líneas que representan las preferencias de cada miembro de la familia. Para cada uno aparece un primer número con la cadena de televisión que querría ver (entre 1 y N) y un segundo número con el canal que bajo ningún concepto permitirá que se vea (obviamente distinto al anterior y también entre 1 y N).
Salida
Por cada caso de prueba se escribirá una línea con tres números. El primero tendrá la cantidad de canales iniciales que permitirían comernos las uvas en paz; el segundo la cantidad de canales que nos llevarán irremediablemente a un bloqueo que no permitirá decidirnos. El último número indica con cuántos canales iniciales el resultado final es indeterminado y dependerá de cómo de ágiles seamos en levantarnos.
Entrada de ejemplo
2 2 1 2 1 2 3 2 2 1 1 2 3 3 1 2 2 1 3 2
Salida de ejemplo
2 0 0 1 2 0 1 0 2