M. Рёбра на кратчайших путях

Неориентированный граф задан списком рёбер. Посчитайте, сколько рёбер лежит хотя бы на одном кратчайшем пути из вершины 1 в вершину $n$.

Ребро $(u, v)$ лежит на кратчайшем пути, если расстояние от 1 до $u$ плюс единица плюс расстояние от $v$ до $n$ равно длине кратчайшего пути — или то же самое с переставленными концами.

Достаточно двух обходов: от вершины 1 и от вершины $n$.

Первая строка содержит числа $n$ ($1 \le n \le 10^5$) и $m$ ($0 \le m \le 2 \cdot 10^5$).

Далее идут $m$ строк с рёбрами простого графа.

Одно число — количество таких рёбер. Если пути нет, выведите 0.