자전거 경주

N개의 도시와 M개의 양방향 도로로 이루어진 연결 그래프가 있다. 도시는 1번부터 N번까지 번호가 매겨져 있다.

다음 세 가지 용어를 사용한다.

• 경로는 앞 도로의 도착 도시와 다음 도로의 시작 도시가 같은 도로들의 연속이다.
• 단순 경로는 같은 도시를 두 번 이상 방문하지 않는 경로이다.
• 링은 시작 도시와 끝 도시가 같은 단순 경로이다.

모든 도시 쌍 사이에는 적어도 하나의 경로가 있으며, 각 도로는 많아야 하나의 링에만 속한다.

도로를 최대 한 번씩만 사용하면서 도시 1에서 끝나는 경주 경로를 만들려고 한다. 시작 도시는 어디든 가능하며, 같은 도시는 여러 번 방문해도 된다. 가능한 경주 경로의 길이 중 최댓값을 구하라. 경로의 길이는 사용한 도로의 수이다.

첫째 줄에 도시의 수 N과 도로의 수 M이 주어진다. (2 ≤ N ≤ 10,000, 1 ≤ M ≤ 2N - 2)

다음 M개 줄에는 서로 다른 두 정수 A와 B가 주어진다. (1 ≤ A, B ≤ N) 이는 A번 도시와 B번 도시를 잇는 양방향 도로를 의미한다. 같은 두 도시를 잇는 도로는 두 개 이상 주어지지 않는다.

도시 1에서 끝나는 가장 긴 경주 경로의 길이를 출력한다.