İmperiya

İmperiya $n$ planetdən ibarətdir və bu planetlər $1$-dən $n$-ə qədər nömrələnmişdir. $1$ nömrəli planet İmperiyanın paytaxtıdır, burada İmperatorun iqamətgahı yerləşir və ordu toplanır. İmperiyanın müxtəlif planetlərində tez-tez üsyanlar baş verir və bunlar dərhal hərbi güclə yatırılmalıdır.

Ordunun sürətli hərəkət etməsi üçün bəzi planetlərdə birtərəfli teleportlar quraşdırılmışdır. Ümumilikdə $m$ teleport mövcuddur. $i$-ci teleport vasitəsilə $a_i$ planetindən $b_i$ planetinə ani keçid mümkündür (əks istiqamətdə deyil). Beləliklə, $x$ planetindəki üsyanı vaxtında yatırmaq mümkündür, əgər $p_1,...,p_k(k\ge 2)$ planetlər ardıcıllığı varsa, burada $p_1=1,p_k=x$ və hər bir $1\le i<k$ üçün $p_i$ nömrəli planetdən $p_{i+1}$ nömrəli planetə teleport mövcuddur. Üsyan yatırıldıqdan sonra ordu nizamı qorumaq üçün planetdə qalır, buna görə də onun paytaxta qayıtması barədə narahat olmağa ehtiyac yoxdur.

Mövcud teleportlarla İmperiyanın istənilən planetindəki üsyanı yatırmaq mümkün olub-olmadığını yoxlayın. Əgər belədirsə, $0$ çıxarın. Əks halda, istənilən planetdəki üsyanı yatırmaq üçün əlavə olaraq tikilməli olan ən az teleport sayını tapın. Hər bir teleport istənilən iki planet arasında tikilə bilər.

Giriş verilənləri

Birinci sətir iki tam ədəd $n$ və $m(2\le n\le 10^5,0\le m\le 2\cdot 10^5)$ ehtiva edir. Növbəti $m$ sətirdən hər biri $a_i,b_i(1\le a_i,b_i\le n)$ cütlüyünü ehtiva edir, bütün $1\le i\le m$ üçün. Heç bir planetdə özünə teleport yoxdur. Heç bir planetdə eyni planetə iki teleport yoxdur.

Çıxış verilənləri

İstənilən planetdəki üsyanı dərhal yatırmaq üçün lazım olan ən az teleport sayını çıxarın.

Nümunələr