Ông Liêm là 1 kẻ trộm bò lừng lẫy, khét tiếng lúc bấy giờ khiến các chủ trang trại nghe tên là hoảng sợ. Ông Hai là 1 chủ trang trại bò lớn tại làng Hòn. Bỗng một ngày nghe tin ông Liêm đã tới làng của mình, ông Hai bèn nghĩ ra cách để đối phó với tên trộm đặc biệt này. Các chuồng bò của ông Hai được đánh số từ \(1\) đến \(n\), có \(m\) công tắc nối giữa \(2\) chuồng. Ban đầu các chuồng bò đều đóng cửa. Nếu ai tác động vào công tắc của một chuồng bất kì thì tất cả các chuồng nối với nó đều thay đổi trạng thái cánh cửa (đóng thành mở, mở thành đóng). Ông Liêm là 1 kẻ trộm tham lam, ông muốn một khi đã trộm thì phải trộm cho hết, do đó ông Liêm nhờ bạn tìm số công tắc tối thiểu cần tác động để mở được tất cả các chuồng bò của ông Hai.

Yêu cầu: Hãy tìm số tác động ít nhất để các cách cửa chuồng bò đều mở? Giả thiết là luôn có phương án để mở tất cả các chuồng bò.

Input

• Dòng 1 chứa 2 số nguyên dương \(n\) và \(m\) (\(1 \le n \le 40\), \(1 \le m \le \frac{n(n-1)}{2}\)).
• \(m\) dòng sau, mỗi dòng ghi 1 cặp số \(a\) và \(b\) tương ứng có một công tắc nối giữa hai chuồng \(a\) and \(b\). Các dây điện nối với công tắc là dây điện hai chiều. Dữ liệu đầu vào được đảm bảo rằng mỗi cặp chuồng \((a, b)\) có duy nhất một công tắc nối giữa chúng.

Output

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

Example

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

3

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n \le 22\).
• Subtask 2 (\(70\%\) số điểm): Không có ràng buộc gì thêm.