색칠 경쟁
시간 제한1초메모리 제한512 MB
앨리스가 연결 그래프의 간선을 두 색으로 칠해 1번에서 N번으로 가는 모든 경로의 색 변화 횟수를 최대화할 때, 그 최댓값을 구한다.
문제
Alice와 Bob은 N개의 정점과 M개의 간선으로 이루어진 단순 연결 그래프에서 게임을 한다.
Alice는 그래프의 각 간선을 빨간색 또는 파란색으로 색칠한다.
경로는 간선의 나열이며, 연속한 두 간선은 공통 정점을 가진다. 이때 두 간선의 색이 다르면 "색 변화"가 일어난다고 한다.
Alice가 그래프를 색칠한 뒤, Bob은 정점 1에서 시작해 정점 N에서 끝나는 경로를 하나 고른다. Bob은 그래프 위의 어떤 경로든 고를 수 있지만, 경로에서 색 변화의 횟수를 최소화하려고 한다. Alice는 Bob이 반드시 겪어야 하는 색 변화의 횟수를 최대화하려고 간선을 색칠한다. Bob이 어떤 경로를 고르더라도 Alice가 강제할 수 있는 색 변화 횟수의 최댓값은 얼마인가?
입력
첫 번째 줄에는 두 정수 N과 M이 주어진다. (2 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000) 다음 M개의 줄에는 정점 ai와 bi를 잇는 무방향 간선을 나타내는 두 정수 ai와 bi가 주어진다. (1 ≤ ai, bi ≤ N, ai ≠ bi)
그래프의 모든 간선은 서로 다르다.
출력
Alice가 정점 1에서 정점 N으로 가는 Bob의 경로에서 강제할 수 있는 색 변화 횟수의 최댓값을 출력한다.