Кратчайший путь в графе

Условие

В первой строке даны число вершин n и число рёбер m. В каждой из следующих m строк даны вершины u и v, соединённые ребром (граф неориентированный). Выведите число рёбер на кратчайшем пути из вершины 1 в вершину n. Если пути нет, выведите -1. Для n = 1 ответ 0.

Примеры

4 4
1 2
2 4
1 3
3 4

2

3 1
2 3

-1

Ограничения

• 1 ≤ n ≤ 10^5
• 0 ≤ m ≤ 2·10^5
• 1 ≤ u, v ≤ n