Qrafiki genişləndirin

Verilmiş istiqamətli qraf $n$ təpə və $m$ qırağa malikdir. Qrafın təpələri $1$-dən $n$-ə qədər nömrələnmişdir. Təpə $1$-dən təpə $n$-ə qədər ən azı bir yolun mövcud olması üçün neçə qırağın istiqamətini dəyişmək lazımdır?

Giriş verilənləri

Birinci sətir iki tam ədəd $n$ və $m(1\le n,m\le 2\cdot 10^6)$ — təpələrin və qıraqların sayını göstərir. Növbəti $m$ sətirdən hər biri iki tam ədəd $x_i$ və $y_i(1\le x_i,y_i\le n)$ ehtiva edir, bu isə $i$-ci istiqamətli qırağın $x_i$ təpəsindən $y_i$ təpəsinə getdiyini göstərir.

Çıxış verilənləri

Dəyişdirilməli olan ən az qıraq sayını çıxarın. Əgər $1$-dən $n$-ə qədər heç bir yol əldə etmək mümkün deyilsə, $-1$ çıxarın.

Nümunələr