Problem
Le fermier John continue de prendre soin de la santé de ses vaches, numérotées consécutivement 1…N.
Récemment, le DF les a tous vérifiés et a découvert que certains d'entre eux étaient malades. En utilisant la vidéo de la grange, le DF peut découvrir quelles paires de vaches ont interagi pour propager la maladie. Le DF a collecté une liste indiquant le moment auquel l'interaction des paires de vaches dans la vidéo (t,x,y) a eu lieu, ce qui signifie qu'au moment t la vache x a interagi avec la vache y. Le FD sait également ce qui suit :
- Exactement une vache a été initialement infectée (patient zéro).
- Une fois qu'une vache est infectée, elle transmet l'infection à ses interactions K suivantes (impliquant éventuellement le même partenaire plusieurs fois). Après K fois de transmission, elle arrête de transmettre l'infection (en réalisant qu'elle infecte, elle commence à bien se laver les sabots).
- Une fois qu'elle tombe malade, elle le reste.
Malheureusement, le PD ne sait pas laquelle de ses N vaches est "Patient Zéro", et il ne connaît pas la valeur de K!. Aidez-le à réduire les plages de ces inconnues en fonction de ses données. La réponse est garantie d'exister.
Entrée
La première ligne d'entrée contient N (2≤N≤100) et T (1≤T≤250). La ligne suivante contient une chaîne de longueur N, composée de 0 et 1, décrivant l'état actuel des vaches N FD, 0 - en bonne santé, 1 - malade. Chacune des lignes T suivantes décrit une entrée de la liste des interactions FD et se compose de trois nombres, t, x, y, où t est un temps d'interaction entier positif (t≤250), x et y sont des entiers différents dans la intervalle 1…N, indiquant quelles vaches ont interagi à l'instant T. Il n'y a pas plus d'une interaction à la fois T.
Mentions légales
Imprimer une ligne contenant trois nombres entiers x, y, z, où x est le nombre de vaches différentes qui pourraient être "patient zéro" y - la plus petite valeur possible de K qui correspond aux données d'entrée z - la plus grande valeur possible de K qui correspond aux données d'entrée S'il n'y a pas de limite supérieure pour K, imprimez "Infinity" ; pour z. Notez que K=0 est possible.
Exemples
| # |
Entrée |
Sortie |
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 Infini |