牛の放牧をよりよく管理するため、Farmer John は農場中に一方通行の牛道を作りました。農場には $1..N$ と番号付けされた $N$ 個の畑があり、各道は2つの畑を結びます。$X$ から $Y$ の道なら $X$ から $Y$ へは進めますが逆はできません。

Bessie はできるだけ多くの畑の草を食べたいです。毎日畑 $1$ から出発し、畑を巡って最後に $1$ に戻ります。各畑で草を食べられるので、異なる訪問先の数を最大にしたいです。同じ畑を何度訪れても食べるのは1回です。

一方通行は訪問先を減らしそうなので不満です。規則を破り、高々1回だけ道を逆向きに進むと、どれだけ食べられるでしょうか。畑 $1$ で始まり終わり、高々1回逆走できる経路の異なる畑の最大数を求めてください。旅全体で逆走は高々1回で、同じ道でも2回逆走できません。

入力

最初の行に畑数 $N$ と道数 $M$（$1 \leq N, M \leq 100,000$）があります。

続く $M$ 行は各道を表し、異なる畑番号 $X$、$Y$ が $X$ から $Y$ の道を示します。同じ道は重複しません。

出力

畑 $1$ で始まり終わり、高々1回逆走できるときの異なる訪問先の最大数を1行で出力します。

入出力例

入力 1

7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7

出力 1

6

注記

入力例の ASCII 図です：

v---3-->6
7   |\  |
^\  v \ |
| \ 1  \|
|  \|   v
|   v   5
4<--2---^

$5$ と $3$ の道を逆走して、$1,2,4,7,2,5,3,1$ を訪問できます。$3$ に着いたら、別の道を逆走せずに $6$ には行けません。

問題作成：Mark Gordon、2015