Empire

The Empire consists of $n$ planets. Lets label these planets with numbers from $1$ to $n$. The planet with the number $1$ is a capital of Empire, where the Emperor residence is located and the troops are prepared. On different planets of the empire the uprisings are often, which must be suppressed by force and immediately.

In order for troops to move quickly, the one-way teleports are installed on some planets. There are $m$ teleports in total. Using the $i$-th teleport you can get instantly from planet $a_i$ to planet $b_i$ (but not vice versa). Thus, it is possible to crush the rebellion in time on some planet $x$, if there is a sequence of planets $p_1,...,p_k(k\ge 2)$ such that $p_1=1,p_k=x$, and for each $1\le i<k$ there is a teleport from planet with number $p_i$ to the planet with number $p_{i+1}$. After crushing the uprising, the troops remain on the planet to maintain the order, so we do not need to worry about their return to the capital.

Check is there an opportunity using the existing system of teleports to crush the rebellion on any planet of the Empire. If so, print $0$. Otherwise find the minimum number of teleports that must be built more so that the rebellion on any planet can be suppressed instantly. Each new teleport can be constructed between any two planets.

Input

The first line contains two integers $n$ and $m(2\le n\le 10^5,0\le m\le 2\cdot 10^5)$. The $i$-th of the next $m$ lines contains the pair of numbers $a_i,b_i(1\le a_i,b_i\le n)$ for all $1\le i\le m$. No one planet has a teleport to itself. No one planet has two teleports to the same planet.

Output

Print the minimum number of teleports, ensuring that the revolt on any planet can be immediately suppressed.

Examples