Problem
El granjero John sigue cuidando la salud de sus vacas, numeradas consecutivamente 1…N.
Recientemente, el FD los revisó a todos y descubrió que algunos de ellos están enfermos. Usando el video del establo, el FD puede averiguar qué pares de vacas interactuaron para propagar la enfermedad. El FD ha recopilado una lista que indica el momento en el que se produjo la interacción de las parejas de vacas del vídeo (t,x,y), lo que significa que en el momento t la vaca x interactuó con la vaca y. El FD también sabe lo siguiente:
- Exactamente una vaca se infectó inicialmente (paciente cero).
- Una vez que una vaca está infectada, transmite la infección a sus próximas interacciones K (posiblemente con la misma pareja varias veces). Después de K tiempos de transmisión, deja de transmitir la infección (al darse cuenta de que está contagiando, comienza a lavarse bien las pezuñas).
- Una vez que se enferma, sigue enferma.
Desafortunadamente, el PD no sabe cuál de sus N vacas es el "Paciente Cero", y no sabe el valor de K!. Ayúdelo a reducir los rangos de estas incógnitas en función de sus datos. Se garantiza que la respuesta existe.
Entrada
La primera línea de entrada contiene N (2≤N≤100) y T (1≤T≤250). La siguiente línea contiene una cadena de longitud N, que consta de 0 y 1, que describe el estado actual de las vacas N FD, 0 - saludable, 1 - enferma. Cada una de las siguientes líneas T describe una entrada de la lista de interacciones FD y consta de tres números, t, x, y, donde t es un tiempo de interacción entero positivo (t≤250), xey son enteros diferentes en el intervalo 1…N, que indica qué vacas interactuaron en el momento T. No se produce más de una interacción en un momento T.
Impresión
Imprima una línea que contenga tres números enteros x, y, z, donde x es el número de vacas diferentes que podrían ser "paciente cero" y - el valor más pequeño posible de K que se ajusta a los datos de entrada z - el valor más grande posible de K que se ajusta a los datos de entrada Si no hay un límite superior para K, imprima "Infinito"; para z. Tenga en cuenta que K=0 es posible.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 Infinito |