Es gibt immer einen Unruhestifter. Farmer John weiß, dass von $N$ Kühen ($1 \le N \le 100$, Nummern1 bis $N$) eine immer lügt, alle anderen immer wahr sprechen. Um sie schnell zu finden, besucht er weidende Kühe einzeln und fragt $Q$ einfache Fragen ($1 \le Q \le 1{,}000$) über Futter (meist ehrlich, aber nicht schlau, verstehen Kühe nur wenige Themen wie Futter). Er schreibt so auf:

Kuh4 sagt,5 frisst mehr Gras als10. Kuh6 sagt,10 frisst mehr als7. Kuh3 sagt,2 frisst mehr als6. Kuh1 sagt,7 frisst mehr als5.

Oben ist die Lügnerin4, 6 oder1. Bestimme die Zahl „möglicher Lügnerinnen“, die gemäß Daten die einzige Lügnerin sein könnten.

Eingabe

• Zeile1: zwei ganze Zahlen mit Leerzeichen $N$, $Q$.
• Zeilen $2..Q+1$: jede Antwort hat3 ganze Zahlen mit Leerzeichen $A$, $B$, $C$; Kuh $A$ sagt, $B$ frisst mehr Gras als $C$. Dieselbe Kuh kann mehrfach erscheinen.

Ausgabe

• Zeile1: eine ganze Zahl, die Zahl möglicher Lügnerinnen.

Beispiele

Eingabe 1

3 4
3 1 2
1 3 1
1 3 2
2 2 1

Ausgabe 1

2

Hinweis

Eingabeerklärung

3 Kühe geben4 Antworten:1 sagt,3 frisst mehr als1 und2;2 sagt,2 mehr als1;3 sagt,1 mehr als2 (Vergleich der Futtermenge).

Ausgabeerklärung

2 oder3 lügt wegen gegensätzlicher Aussagen. Wäre1 Lügnerin, könnten2 und3 nicht lügen, also muss1 wahr sprechen.

Aufgabenautor: Brian Dean, 2004