Farmer John은 $1..N$번으로 매긴 헛간 $N$개($1 \le N \le 1{,}000$)를 새 광섬유망으로 연결하려 합니다. 큰 연못 둘레에 원으로 있어 이웃 헛간끼리만 연결할 수 있으며 $N$번은 1번과 이웃합니다.

특정 소 쌍만 통신하려 하므로 모두 연결할 필요는 없습니다. 모든 요구 쌍이 망으로 통신하게 하면서 연결 수를 최소화합니다. 요구 목록으로 최소 선 수를 구하세요. 1번에서 3번으로 통신하려면 1-2와 2-3 선을 설치해야 합니다.

입력

• $1$번 줄: 정수 $N$, $P$. 뒤 수는 통신 쌍 수($1 \le P \le 10{,}000$).

• $2..P+1$번 줄: 통신을 원하는 헛간 쌍의 정수 두 개. 중복 쌍은 없습니다.

출력

한 줄에 필요한 최소 직접 연결 수 정수 하나.

예제

입력 1

5 2
1 3
4 5

출력 1

3

참고

헛간 쌍 1-2, 2-3, 4-5를 연결합니다.

문제 제공: Reid Barton, 2001.