群れにはいつも問題児がいます。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行目：空白区切り2整数 $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