Farmer John muốn nối $N$ chuồng ($1 \le N \le 1{,}000$), đánh số $1..N$, bằng mạng cáp quang mới. Chúng nằm vòng tròn quanh hồ lớn, nên chỉ nối được chuồng kề; chuồng $N$ kề chuồng 1.

Không cần nối tất cả: chỉ vài cặp bò muốn liên lạc. Muốn ít kết nối nhất nhưng mọi cặp yêu cầu vẫn liên lạc qua mạng. Cho danh sách cặp, tìm số đường ít nhất. Để liên lạc 1 tới 3 cần nối 1-2 và 2-3.

Dữ liệu vào

• Dòng $1$: số nguyên $N$ và $P$, số sau là số cặp ($1 \le P \le 10{,}000$).

• Các dòng $2..P+1$: hai số nguyên mô tả cặp chuồng cần liên lạc. Không cặp trùng.

Dữ liệu ra

Một dòng với số nguyên, số kết nối trực tiếp ít nhất.

Ví dụ

Dữ liệu vào 1

5 2
1 3
4 5

Dữ liệu ra 1

3

Ghi chú

Chúng nối các cặp 1-2, 2-3 và 4-5.

Nguồn bài: Reid Barton, 2001.