Bicycle Slopes (Fahrradsteigungen)
Emil möchte mit seinem Fahrrad von Stadt
1 nach Stadt n reisen. Allerdings stellen die Straßen, die diese Städte verbinden, eine Herausforderung dar. Jede Straße hat eine Neigung – entweder bergauf oder bergab. Immer wenn Emil von einer bergauf führenden Straße auf eine bergab führende Straße (oder umgekehrt) wechselt, muss er einen Gangwechsel vornehmen, um die Fahrt angenehm zu halten. Emil möchte wissen, wie oft er während seines gesamten Weges von Stadt 1 nach Stadt n den Fahrradgang wechseln muss.#### Output
Input
Die erste Zeile enthält zwei durch Leerzeichen getrennte ganze Zahlen,
n und m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000). Sie geben die Anzahl der Städte sowie die Anzahl der Straßen an.Die nächsten
m Zeilen enthalten jeweils zwei durch Leerzeichen getrennte ganze Zahlen und (, ), die eine Straße zwischen den Städten und beschreiben. Die Straße von nach führt bergauf, weshalb die Straße von nach bergab verläuft.Output
Das Programm soll eine einzelne Zahl ausgeben, die angibt, wie oft Emil mindestens den Gang wechseln muss, um von Stadt
1 nach Stadt n zu gelangen.Examples
Eingabe | Ausgabe |
5 5
1 2
2 3
5 3
4 2
4 5 | 1 |
3 3
1 2
2 3
3 1 | 0 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB