هناك دائمًا مشاغبة. عرف 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