Problem
L'allevatore John continua a prendersi cura della salute delle sue mucche, numerate consecutivamente 1…N.
Di recente, il FD li ha controllati tutti e ha scoperto che alcuni di loro sono malati. Utilizzando il video della stalla, l'FD può scoprire quali coppie di mucche hanno interagito per diffondere la malattia. Il FD ha raccolto un elenco che indica l'ora in cui è avvenuta l'interazione delle coppie di vacche nel video (t,x,y), il che significa che all'istante t la vacca x ha interagito con la vacca y. La FD sa anche quanto segue:
- Esattamente una vacca è stata inizialmente infettata (paziente zero).
- Una volta che una mucca è stata infettata, trasmette l'infezione alle sue successive interazioni K (possibilmente coinvolgendo lo stesso partner più volte). Dopo K volte di trasmissione, smette di trasmettere l'infezione (rendendosi conto che sta infettando, inizia a lavarsi accuratamente gli zoccoli).
- Una volta che si ammala, rimane malata.
Purtroppo il Pd non sa quale delle sue vacche N sia "Paziente Zero", e non conosce il valore di K!. Aiutalo a restringere il campo di queste incognite in base ai suoi dati. La risposta esiste sicuramente.
Inserimento
La prima riga di input contiene N (2≤N≤100) e T (1≤T≤250). La riga successiva contiene una stringa di lunghezza N, composta da 0 e 1, che descrive lo stato attuale di N vacche FD, 0 - sane, 1 - malate. Ciascuna delle seguenti linee T descrive una voce dall'elenco delle interazioni FD e consiste di tre numeri, t, x, y, dove t è un tempo di interazione intero positivo (t≤250), x e y sono numeri interi diversi nel intervallo 1…N,, che indica quali bovine hanno interagito all'istante T. Non si verifica più di un'interazione alla volta T.
Impressum
Stampa una riga contenente tre numeri interi x, y, z, dove x è il numero di vacche diverse che potrebbero essere "paziente zero" y - il valore più piccolo possibile di K che si adatta ai dati di input z - il valore più grande possibile di K che si adatta ai dati di input Se non esiste un limite superiore per K, print "Infinito"; per z. Si noti che K=0 è possibile.
Esempi
| # |
Input |
Uscita |
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 Infinito |