Il y a toujours une trouble-fête. Farmer John sait que parmi $N$ vaches ($1 \le N \le 100$, numéros1 à $N$), une ment toujours et les autres disent toujours vrai. Pour la trouver vite, il visite les vaches au pâturage une à une et pose $Q$ questions simples ($1 \le Q \le 1{,}000$) sur la nourriture (assez honnêtes mais peu intelligentes, elles comprennent peu de sujets hormis la nourriture). Il note ainsi :

Vache4 dit que5 mange plus d’herbe que10. Vache6 dit que10 mange plus que7. Vache3 dit que2 mange plus que6. Vache1 dit que7 mange plus que5.

La menteuse ci-dessus est4, 6 ou1. Calculez le nombre de vaches «potentiellement menteuses», pouvant être l’unique menteuse d’après les données.

Entrée

• Ligne1 : deux entiers séparés par un espace $N$, $Q$.
• Lignes $2..Q+1$ : chaque réponse a3 entiers séparés par des espaces $A$, $B$, $C$ ; vache $A$ dit que $B$ mange plus d’herbe que $C$. La même vache peut apparaître plusieurs fois.

Sortie

• Ligne1 : un entier, le nombre de menteuses potentielles.

Exemples

Entrée 1

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

Sortie 1

2

Remarque

Explication de l’entrée

3 vaches donnent4 réponses :1 dit que3 mange plus que1 et2 ;2 dit que2 plus que1 ;3 dit que1 plus que2 (comparaison de quantité mangée).

Explication de la sortie

2 ou3 ment car leurs déclarations sont opposées. Si1 mentait,2 et3 ne pourraient mentir, donc1 dit vrai.

Auteur du problème : Brian Dean, 2004