В стаде есть нарушитель. 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$: каждый ответ —3 целых через пробел $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