Trên đường đi dã ngoại, Alice đố Bob một bài toán như sau:

Cho một tập hợp ~S~ gồm các số nguyên từ ~1~ đến ~n~, và cho ~m~ cặp số ~A_i~ và ~B_i~ (~A_i \neq B_i~). Hãy tìm số nguyên ~k~ nhỏ nhất sao cho mọi tập con có đúng ~k~ phần tử của ~S~ phải chứa ít nhất một trong ~m~ cặp số đã cho, hay nói cách khác, mọi tập con có ~k~ phần tử của ~S~ phải chứa ít nhất một cặp ~A_i~ và ~B_i~.

Hãy giải quyết bài toán trên cùng Bob nhé.

Yêu cầu: Tìm số nguyên ~k~ nhỏ nhất thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên gồm hai số nguyên ~n, m~.
• ~m~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~A_i~ và ~B_i~.

Output

• Gồm 1 dòng duy nhất là kết quả bài toán.

Sample Input 1

4 4
1 3
2 3
2 4
1 4

Sample Output 1

3