레이팅 미적용설명
어떤 나라에서 자전거 경주가 열린다. 이 나라의 교통망은 \(1\)부터 \(N\)까지 번호가 붙은 \(N\)개의 도시와, 이들을 연결하는 \(M\)개의 양방향 도로로 이루어져 있다. 다음 용어를 사용하기로 한다:
- 경로란 각 도로가 바로 앞 도로가 끝난 도시에서 시작하는 도로들의 나열이다.
- 단순 경로란 어떤 도시도 두 번 이상 방문하지 않는 경로이다.
- 고리란 시작한 도시에서 끝나는 단순 경로이다.
교통망은 모든 도시 쌍 사이에 경로가 적어도 하나 존재하도록 되어 있다. 또한 교통망의 모든 도로는 많아야 하나의 고리에 속한다.
다음 두 조건을 만족하는, 경주를 위한 가장 긴 경로를 찾는 것이 여러분의 과제이다:
- 경로는 어느 도시에서 시작해도 되지만, 반드시 도시 \(1\)에서 끝나야 한다.
- 경로는 한 도시를 여러 번 방문해도 되지만, 어떤 도로도 두 번 이상 포함하면 안 된다.
제약
입력 형식
입력의 첫째 줄에 두 정수 \(N\)과 \(M\) (\(2 \le N \le 10\,000\), \(1 \le M \le 2N - 2\))이 주어진다 — 교통망의 도시 수와 도로 수이다.
다음 \(M\)개의 줄에는 서로 다른 두 정수 \(A\)와 \(B\) (\(1 \le A, B \le N\))가 주어진다. 도시 \(A\)와 \(B\) 사이에 양방향 도로가 있다는 뜻이다. 어떤 두 도시도 두 개 이상의 도로로 직접 연결되어 있지 않다.
출력 형식
가장 긴 경주 경로의 길이를 한 줄에 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 90점 |
예제 1
입력
4 3
1 2
1 3
2 4출력
2예제 2
입력
6 6
1 2
1 3
2 4
3 4
3 5
5 6출력
5예제 3
입력
5 6
1 2
2 3
3 4
4 5
5 3
3 1출력
6문제 정보
태그