Problem
O fazendeiro John continua cuidando da saúde de suas vacas, consecutivamente numeradas 1…N.
Recentemente, o FD verificou todos eles e descobriu que alguns deles estão doentes. Usando o vídeo do celeiro, o FD pode descobrir quais pares de vacas interagiram para espalhar a doença. O DF coletou uma lista indicando o momento em que ocorreu a interação dos pares de vacas no vídeo (t,x,y), significando que no momento t a vaca x interagiu com a vaca y. O DF também sabe o seguinte:
- Exatamente uma vaca foi inicialmente infectada (paciente zero).
- Uma vez que uma vaca é infectada, ela passa a infecção para suas próximas K interações (possivelmente envolvendo o mesmo parceiro várias vezes). Após K vezes de transmissão, ela para de transmitir a infecção (ao perceber que está infectando, ela começa a lavar bem os cascos).
- Quando ela fica doente, ela fica doente.
Infelizmente, o PD não sabe qual de suas N vacas é "Paciente Zero" e não sabe o valor de K!. Ajude-o a reduzir os intervalos dessas incógnitas com base em seus dados. A resposta com certeza existe.
Entrada
A primeira linha de entrada contém N (2≤N≤100) e T (1≤T≤250). A próxima linha contém uma string de comprimento N, consistindo de 0 e 1, descrevendo o estado atual de N vacas FD, 0 - saudável, 1 - doente. Cada uma das T linhas a seguir descreve uma entrada da lista de interações FD e consiste em três números, t, x, y, onde t é um tempo de interação inteiro positivo (t≤250), x e y são inteiros diferentes no intervalo 1…N,, indicando quais vacas interagiram no tempo T. Não ocorre mais de uma interação ao mesmo tempo T.
Impressão
Imprima uma linha contendo três inteiros x, y, z, onde x é o número de vacas diferentes que poderiam ser "paciente zero" y - o menor valor possível de K que se ajusta aos dados de entrada z - o maior valor possível de K que se ajusta aos dados de entrada Se não houver limite superior para K, imprima "Infinito"; para z. Note que K=0 é possível.
Exemplos
| # |
Entrada |
Saída |
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 Infinito |