問題文

魔法使いのコアさんは、$1,2,\dots,N$ の番号が付いた $N$ 個の魔石を研究しています。

魔石 $i$ $(1 \leq i \leq N)$ は大きさ $m_{i}$ の魔力を持っており、次の $M$ 個の条件（以下「前提」と呼ぶ）をすべて満たします。

• $m_{A_{j} } \geq m_{B_{j} }$ $(1 \leq j \leq M)$

ただし、$M=0$ の場合、前提は何も与えられません。

これから、コアさんは次の操作（以下「鑑定」と呼ぶ）を $0$ 回以上好きな回数だけ行います。

• $1 \leq x,y \leq N$ を満たす異なる整数の組 $(x,y)$ を $1$ つ選び、鑑定魔法を使う。
  $m_{x} \geq m_{y}$ ならば「$m_{x} \geq m_{y}$ 」という情報、そうでなければ「$m_{x} < m_{y}$ 」という情報が得られる。

コアさんが鑑定を $n$ 回行い、そこで得た $n$ 個の情報と先の前提を照らし合わせたところ、
$m_{1} = m_{2} = \dots = m_{N}$ が確実に成り立つことが証明されました。

このとき、$n$ の値としてあり得るものの最小値を求めてください。

制約

• $2 \leq N \leq 10^{5}$

• $\displaystyle 0 \leq M \leq \min ( 2 \times 10^{5}, N \times (N-1) )$

• $1 \leq A_{j},B_{j} \leq N$ $(1 \leq j \leq M)$

• $A_{j} \neq B_{j}$ $(1 \leq j \leq M)$

• $(A_{i},B_{i}) \neq (A_{j},B_{j})$ $(1 \leq i < j \leq M)$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$ $M$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
   $\vdots$
$A_{M}$ $B_{M}$

• $1$ 行目には $N$ と $M$ がこの順に半角スペース区切りで与えられる

• $(1+j)$ $(1 \leq j \leq M)$ 行目には $A_{j}$ と $B_{j}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

3 2
1 2
2 3

1

4 0

4

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

0

100000 2
1 2
2 1

99999