3. Turistika na Orave

Takmer každý si niekedy povedal, že by chcel byť turistom. Chodiť viac na čerstvý vzduch, spoznať okolitú prírodu, vyvetrať trochu hlavu, ktorú často núti riešiť nezmyselné informatické problémy. Aj Samo mal nedávno takéto myšlienky. A keďže čo si Samo zmyslí, to aj urobí, rozhodol sa ísť na poriadnu túru. Samozrejme, počas riadnej túry sa nemôže len tak túlať po Orave, túru treba dobre naplánovať. Vyznačil si preto na mape \(n\) prírodných krás. Medzi nimi vedie \(m\) turistických chodníčkov. Aby sa na Orave vyhlo cestovným nehodám, každým chodníčkom je povolené prejsť len v jednom smere. (Je možné, že medzi niektorými dvojicami prírodných krás vedú dva chodníčky – jeden tam a druhý späť.)

Navyše platí, že na Orave sa nedá dlho blúdiť. Oravská chodníčková sieť má totiž jednu zaujímavú vlastnosť: Nech by ste svoju prechádzku začali pri ktorejkoľvek prírodnej kráse, ak ju na tom istom mieste chcete aj skončiť, je zaručené, že viete navštíviť nanajvýš štyri rôzne iné prírodné krásy – a to bez ohľadu na to, ako budete chodiť a či niektoré prírodné krásy (vrátane tej, kde ste začali a skončili) navštívite viackrát.

Samo si chce naplánovať túru Oravskou prírodou. Aby celému svetu dokázal, že to myslí vážne, s každou krásou prírody sa odfotí a albumy potom rozdá v škole. Aby album vyzeral čo najúžasnejšie, Samo by chcel nájsť takú turistickú trasu, na ktorej sa zastaví na čo najväčšom počte prírodných krás. Navyše však musí platiť, že pri žiadnej prírodnej kráse nebude dvakrát – aj tak za ňu ďalšiu fotku do albumu nedostane, tak by sa mu ku nej fakt nechcelo zbytočne kráčať.

Formát vstupu

Orava je orientovaný graf ktorého vrcholy (prírodné krásy) sú očíslované od \(1\) po \(n \leq 10^5\). Tento graf má \(m \leq 10^6\) jednosmerných hrán (chodníčkov). Prvý riadok vstupu obsahuje čísla \(n\) a \(m\).

Nasledovných \(m\) riadkov vstupu popisuje chodníčky. V každom z týchto riadkov sú dve čísla \(1 \leq a, b \leq n\), ktoré uvádzajú že sa dá priamym chodníčkom dostať od krásy \(a\) ku kráse \(b\). Je zaručené, že graf chodníčkov nemá slučky ani násobné hrany. Je tiež zaručené, že tento graf má vlastnosť popísanú v druhom odseku zadania.

Sú štyri testovacie sady. Postupne v nich platí \(n\leq 10\) a \(m\leq 20\), \(n\leq 200\) a \(m\leq 1\,200\), \(n\leq 1\,000\) a \(m\leq 5\,000\), \(n\leq 100\,000\) a \(m\leq 1\,000\,000\).

Formát výstupu

Vypíšte jeden riadok a v ňom jedno číslo: maximálny počet prírodných krás, ktoré Samo dokáže navštíviť počas svojej túry. Túru môže začat aj skončiť pri ľubovoľnej prírodnej kráse (dopravu k prvej kráse a od poslednej krásy si zabezpečí).

Príklady

Input:

4 4
1 3
1 2
2 1
4 1

Output:

3

Samo napríklad navštívi prírodné krásy v poradí 4-1-2. Nemôže ísť 4-1-2-1-3, pretože by krásu číslo 1 navštívil dvakrát.