Імперія

Імперія включає у себе $n$ планет. Пронумеруємо ці планети числами від $1$ до $n$. Планета з номером $1$ — столиця Імперії, де знаходиться резиденція Імператора і збирається військо. На різних планетах імперїї часто спалахують повстання, які приходиться придушувати військовою силою і відразу ж.

Для того, щоб військо могло швидко пересуватись, на деяких планетах встановлені односторонні телепорти. Всього телепортів $m$ штук. За допомогою $i$-ого телепорта можна миттєво потрапити з планети $a_i$ на планету $b_i$ (але не навпаки). Таким чином, своєчасно придушити повстання на деякій планеті $x$ можна, якщо існує послідовність планет $p_1,...,p_k(k\ge 2)$ така, що $p_1=1,p_k=x$, а для кожного $1\le i<k$ є телепорт з планети з номером $p_i$ на планету з номером $p_{i+1}$. Враховуючи, що після придушення повстання військо залишається на планеті для підтримання порядку, про його повернення у столицю ми можемо не турбуватись.

Перевірте, чи є можливість при наявних телепортах придушити повстання на довільній планеті Імперії. Якщо це так, виведіть $0$. У противному випадку, знайдіть найменшу кількість телепортів, які потрібно додатково побудувати, щоб повстання на довільній планеті було придушено. Кожен телепорт може бути збудовано між довільними двома планетами.

Вхідні дані

Перший рядок містить два цілих числа $n$ та $m(2\le n\le 10^5,0\le m\le 2\cdot 10^5)$. $i$-ий з наступних $m$ рядків містить пару чисел $a_i,b_i(1\le a_i,b_i\le n)$ для усіх $1\le i\le m$. На жодній з планет немає телепорту на саму себе. На жодній планеті немає двох телепортів на одну і ту ж планету.

Вихідні дані

Виведіть найменшу кількість телепортів, гарантуючих, що повстання на довільній планеті можна буде негайно придушити.

Приклади