시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 3 2 22.222%

문제

상그니 아라비아는 세계에서 오일 머니를 가장 많이 보유하는 나라이다. 국왕으로 재직중인 고둘라 창지즈 영사우드는 천연 자원의 위대함을 알리기 위해서 자전거 레이싱 경기를 개최하기로 결심했다. 

이 나라에는 도시가 N개가 있으며, 그 도시는 M개의 양방향 도로로 연결되어 있다. 도시는 1번부터 N번까지 번호가 매겨져 있다. 자전거 레이싱 트랙을 결정하기 위해서, 상근이는 아래와 같은 용어 세 가지를 사용할 것이다.

1. 경로는 각 도로의 도착점과 다음 도로의 시작점이 같은 도로의 연속이다.

2. 단순 경로는 한 도시를 두 번 이상 방문하지 않는 경로이다.

3. 링은 시작 도시와 끝나는 도시가 같은 단순 경로이다.

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

다음 두 가지 조건을 만족하는 가장 긴 레이싱 경로를 찾는 프로그램을 작성하시오.

1. 경로의 시작 도시는 어느 곳이 되어도 상관없지만, 도착 도시는 1이어야 한다.

2. 한 도시를 한 번 이상 방문해도 된다. 하지만, 도로는 최대 한 번만 지날 수 있다.

입력

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

다음 M개 줄에는 서로 다른 두 정수 A와 B가 주어진다. (1 ≤ A, B ≤ N) 두 숫자는 도로의 정보를 나타내며, A와 B를 연결하는 양방향 도로이다. 두 도시를 연결하는 도로가 두 개 이상인 경우는 없다.

출력

첫째 줄에 가장 긴 레이싱 경로의 길이를 출력한다.

예제 입력

6 6
1 2
1 3
2 4
3 4
3 5
5 6

예제 출력

5

힌트