Империя

Империя включает в себя $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$. Ни на одной планете нет телепорта в саму себя. Ни на одной планете нет двух телепортов на одну и ту же планету.

Выходные данные

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

Примеры