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

입력 형식

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

출력 형식

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

예제 입력 1

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

예제 출력 1

2

예제 입력 2

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

예제 출력 2

3

예제 입력 3

7 8
1 3
1 4
3 5
4 5
5 6
5 7
6 2
7 2

예제 출력 3

1