On Average They're Purple

Alice와 Bob이 $N$개의 정점과 $M$개의 간선을 가진 단순 연결 그래프에서 게임을 한다.

Alice는 그래프의 각 간선을 빨간색 또는 파란색으로 칠한다.

경로는 연속한 두 간선이 공통 정점을 가지는 간선의 나열이다. 연속한 두 간선의 색이 다르면 "색 변화"가 일어난다.

Alice가 그래프를 칠한 뒤, Bob은 정점 $1$에서 시작해 정점 $N$에서 끝나는 경로를 하나 고른다. Bob은 그래프 위의 어떤 경로든 고를 수 있지만, 경로에서 색 변화의 수를 최소화하려고 한다. Alice는 Bob이 반드시 겪어야 하는 색 변화의 수를 최대화하려고 한다. Bob이 어떤 경로를 고르더라도 Alice가 강제할 수 있는 색 변화의 수의 최댓값은 얼마인가?

첫째 줄에 두 정수 $N$과 $M$이 주어진다. ($2 \le N \le 100\,000$, $1 \le M \le 100\,000$) 다음 $M$개의 줄에 정점 $a\_i$와 $b\_i$를 잇는 무방향 간선을 나타내는 두 정수 $a\_i$, $b\_i$가 주어진다. ($1 \le a\_i, b\_i \le N$, $a\_i \not= b\_i$)

그래프의 모든 간선은 서로 다르다.

Alice가 정점 $1$에서 정점 $N$으로 가는 Bob의 경로에서 강제할 수 있는 색 변화의 수의 최댓값을 출력한다.