תמיד יש עושה צרות. Farmer John יודע שמתוך $N$ פרות ($1 \le N \le 100$, מספרים1 עד $N$) אחת תמיד משקרת והשאר תמיד אמת. כדי למצוא מהר מבקר ברועות אחת אחת ושואל $Q$ שאלות פשוטות ($1 \le Q \le 1{,}000$) על כמות האוכל (לרוב כנות אך לא חכמות, מזון מהנושאים המעטים שהן מבינות). רושם כך:

פרה4 אומרת ש־5 אוכלת יותר עשב מ־10. פרה6 אומרת ש־10 יותר מ־7. פרה3 אומרת ש־2 יותר מ־6. פרה1 אומרת ש־7 יותר מ־5.

לעיל המשקרת4, 6 או1. מצאו מספר «משקרות אפשריות», היכולות להיות המשקרת היחידה לפי הנתונים.

קלט

• שורה1: שני שלמים ברווח $N$, $Q$.
• שורות $2..Q+1$: כל תשובה שלושה שלמים ברווחים $A$, $B$, $C$; פרה $A$ אומרת ש־$B$ אוכלת יותר עשב מ־$C$. אותה פרה עשויה להופיע שוב.

פלט

• שורה1: שלם, מספר המשקרות האפשריות.

דוגמאות

קלט 1

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

פלט 1

2

הערה

הסבר הקלט

3 פרות נותנות4 תשובות:1 אומרת ש־3 אוכלת יותר מ־1 ומ־2;2 אומרת ש־2 יותר מ־1;3 אומרת ש־1 יותר מ־2 (השוואת כמות אוכל).

הסבר הפלט

2 או3 משקרת כי האמירות הפוכות. אילו1 שיקרה,2 ו־3 לא יכלו לשקר, ולכן1 אמת.

מחבר הבעיה: Brian Dean, 2004