Module: Lineare Überbrückung

Problem

Farmer John kümmert sich weiterhin um die Gesundheit seiner Kühe, konsequent nummeriert 1...N.
FD überprüfte sie vor kurzem alle und fand, dass einige von ihnen krank waren. Mit einem Video aus der Scheune kann FD herausfinden, welche Kühe bei der Ausbreitung der Krankheit interagierten. Die FD sammelte eine Liste, in der die Zeit angezeigt wurde, in der ein paar Kühe in einem Video (t,x,y) interagierten, was darauf hindeutete, dass zum Zeitpunkt t die Kuh mit der Kuh y interagierte. Die FD kennt auch Folgendes:

1. Eine Kuh wurde zunächst infiziert (kein Patient).
2. Nach der Infizierung wird die Kuh auf die nächsten K-Interaktionen übertragen (möglicherweise auch der gleiche Partner mehrmals). Nach K, wenn die Infektionen übertragen werden, hört es auf, die Infektion zu übertragen (erkennt, dass es kontaminiert, es beginnt Waschen.)
3. Einmal krank, bleibt sie krank.

Leider weiß FD nicht, welche seiner N Kühe ein Nullpatient ist, und er kennt nicht die Bedeutung von K! Helfen Sie ihm, die Reichweiten dieser Unbekannten basierend auf seinen Daten zu verengen. Die Antwort ist garantiert.

Eingangsdaten
Die erste Eintragslinie enthält N (2 ≤ N100) und T (1 ≤ T250). Die nächste Zeile enthält eine Linie von N Länge bestehend aus 0 und 1 beschreiben den aktuellen Zustand von N Kühen, 0 gesund, 1 krank. Jede der folgenden T-Zeilen beschreibt die Liste der Interaktionen der FD, und besteht aus drei Zahlen, t, x, y, wobei t die positive ganze Zeit der Interaktion (t250) x und y - die unterschiedlichen Gesamtheiten von 1...N ist, was anzeigt, welche Kühe zum Zeitpunkt von T interagierten. Zu einem Zeitpunkt hat T nicht mehr als eine Interaktion.
Ausgangsdaten
Legen Sie eine Zeile aus, die drei ganze Zahlen x, y, z enthält, wobei x die Anzahl der verschiedenen Kühe ist, die ein Null-Patient y gewesen sein kann, der minimal mögliche K-Wert, der der Basislinie z passt -- der höchstmögliche K-Wert zu den Originaldaten, wenn es keine Obergrenze für K gibt, gehen Sie für z zu "Infinity". Wir werden bemerken, dass vielleicht K=0.

Beispiele

Nein	Eingangsdaten	Ausgangsdaten
1	4 3 1100 Artikel 2 2 3 6 2 4	1 1 Unendlichkeit