Luôn có con gây rối. Farmer John biết trong $N$ bò ($1 \le N \le 100$, số1 tới $N$) có một luôn nói dối, còn lại luôn thật. Muốn tìm nhanh nên lần lượt tới bò đang gặm cỏ, hỏi $Q$ câu đơn giản ($1 \le Q \le 1{,}000$) về lượng ăn (dù đa số thật thà, bò ít thông minh, thức ăn là một trong ít chủ đề hiểu). Ghi như sau:

Bò4 nói5 ăn cỏ hơn10. Bò6 nói10 ăn hơn7. Bò3 nói2 ăn hơn6. Bò1 nói7 ăn hơn5.

Trên đây bò nói dối là4, 6 hoặc1. Tìm số bò «có thể nói dối», nghĩa là có thể là con nói dối duy nhất theo dữ liệu.

Dữ liệu vào

• Dòng1: hai số nguyên cách dấu cách $N$, $Q$.
• Các dòng $2..Q+1$: mỗi trả lời có3 số nguyên cách dấu cách $A$, $B$, $C$; bò $A$ nói $B$ ăn cỏ hơn $C$. Một bò có thể xuất hiện nhiều lần.

Dữ liệu ra

• Dòng1: số nguyên, số bò có thể nói dối.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2

Ghi chú

Chi tiết đầu vào

3 bò cho4 trả lời:1 nói3 ăn hơn1 và2;2 nói2 hơn1;3 nói1 hơn2 (so sánh lượng ăn).

Chi tiết đầu ra

2 hoặc3 nói dối vì lời đối lập. Nếu1 nói dối,2 và3 không thể dối, nên1 phải nói thật.

Tác giả bài toán: Brian Dean, 2004