Có ~N~ bóng đèn (đánh số từ 1 đến ~N~) và ~M~ đoạn dây nối giữa 2 bóng đèn. Ban đầu tất cả các bóng đèn đều tắt.

Nếu bạn thay đổi tác động vào 1 bóng đèn thì tất cả các bóng đèn nối với nó đều thay đổi theo tác động đó (tắt thành bật, bật thành tắt).

Yêu cầu: Tìm số tác động ít nhất để các bóng đèn đều sáng. Giả thiết là luôn có phương án để bật sáng tất cả bóng đèn.

Input

• Dòng 1 chứa 2 số nguyên dương ~N~ và ~M~ (~1 \le N \le 35, 1 \le M \le 595~)
• ~M~ dòng sau, mỗi dòng ghi 1 cặp số ~a~ và ~b~ tương ứng có dây nối 2 bóng đèn ~a~ và ~b~.

Output

• Một số duy nhất là số tác động ít nhất.

Sample Input 1

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

Sample Output 1

3