Юниорская олимпиада по информатике 2022 года за 7 класс | Казахстанские олимпиады

Задача C. Ice Cream

Есть $N$ городов. Города соединены двусторонними дорогами. Все дороги имеют длину $1$. Гарантируется что можно добраться от любого города до любого другого.

Вас просят найти длину второго по длине кратчайшего пути от города $1$ до города $N$.

Формат входного файла

Дается $N$ и $M$($1$ $\leq$ $N$ $\leq$ $200000$, $1$ $\leq$ $M$ $\leq$ $500000$) - количество городов и количество дорог.

Далее идет $M$ строк в каждой строке описаны дороги $ai$, $bi$ ($1$ $\leq$ $ai$, $bi$ $\leq$ $200000$) - города которые соединены дорогой.

Формат выходного файла

Вывести длину второго кратчайшейго пути от города $1$ до города $N$.

Примеры

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

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