Велосипедные склоны

Эмиль намерен добраться из города 1 в город n на велосипеде. Однако дороги, соединяющие эти города, представляют определённую сложность: каждая из них идёт либо в гору, либо с горы. Если Эмиль переезжает с подъёмной дороги на спуск или наоборот, ему приходится переключать велосипедную передачу, чтобы поездка оставалась комфортной. Эмиля интересует, какое минимальное количество раз во время пути от города 1 до города n ему нужно будет переключить передачу.

Выведите минимальное количество переключений передач, необходимое, чтобы доехать от города 1 до города n.

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

Первая строка содержит два разделённых пробелом числа n и m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000), означающие количество городов и количество дорог соответственно.

Каждая из следующих m строк содержит по два разделённых пробелом числа и (, ), которые указывают, что есть дорога между городами и . Дорога из в идёт в гору, а в обратном направлении ( в ) — с горы.

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

Программа должна вывести одно число — минимальное количество переключений передач, которое понадобится Эмилю на пути от города 1 до города n.

Примеры