시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 625 159 110 25.000%

문제

N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이 때 한 번 방문했던 도시(1, 2번 도시 제외)를 두 번 이상 방문하지 않으려 한다. 한 번 1번 도시와 2번 도시 사이를 오갈 때, 반드시 한 개 이상의 도시를 중간에 거쳐야 한다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다.

입력

첫째 줄에 두 정수 N(3≤N≤400), P(1≤P≤10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 서로 다른 두 도시의 번호가 주어진다.

출력

첫째 줄에 왔다 갔다 할 수 있는 최대 회수를 출력한다.

예제 입력

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

예제 출력

2

힌트