There's always one troublemaker in the herd. Farmer John has determined that one of his $N$ cows ($1 \le N \le 100$; cows are numbered 1..$N$) always tells lies even though all the remaining cows always tell the truth. He wants to find this troublesome cow as quickly as possible. To do so, he visits the cows one-by-one as they graze in the pasture and asks them $Q$ ($1 \le Q \le 1{,}000$) simple questions about the amount of food they eat (though mostly honest, cows are still relatively unintelligent and food is one of the few topics they understand). He writes down the results of his questions in the following form:
Cow #4 says that cow #5 eats more grass than cow #10. Cow #6 says that cow #10 eats more grass than cow #7. Cow #3 says that cow #2 eats more grass than cow #6. Cow #1 says that cow #7 eats more grass than cow #5.
In the example above, it is clear that the untruthful cow must be either cow #4, cow #6, or cow #1. Your task is to determine the number of "potentially untruthful" cows based on their responses. A potentially untruthful cow is a cow that could conceivably be the one that tells lies, judging by the input data provided.
Input
- Line 1: Two space-separated integers: $N$ and $Q$
- Lines $2..Q+1$: Each line describes a question response and contains 3 space-separated integers: $A$ $B$ $C$, meaning that cow $A$ says that cow $B$ eats more grass than cow $C$. The same cow might appear several times in this list.
Output
- Line 1: A single line with a single integer that is the number of potentially untruthful cows.
Examples
Input 1
3 4
3 1 2
1 3 1
1 3 2
2 2 1Output 1
2Input Details
3 cows give 4 responses. Cow 1 says that cow3>cow1 and cow3>cow2, Cow 2 says that cow2>cow1 and Cow 3 says that cow1>cow2. (Of course, ">" means "eats more than".)
Output Details
It's easy to see that either cow 2 or cow 3 is lying since their statements are opposites. If cow 1 was the liar, then neither cow 2 nor cow 3 could be lying, thus cow 1 must be telling the truth.
Problem credits: Brian Dean, 2004