Tập con

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\ne 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 cả hai số $A_i$ và $B_i$ của ít nhất một cặp $i$ nào đó.

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.

Dữ liệu vào

• 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$ ($1\le A_i,B_i\le n$, $A_i\ne B_i$). Các cặp có thể lặp lại.

Dữ liệu ra

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

Ràng buộc

• $2\le n\le 80$, $1\le m\le 100$.
• Gọi $x$ là số cặp chỉ số $(i,j)$ với $1\le i,j\le m$, $i\ne j$ sao cho $A_i=B_j$. Mỗi test thỏa mãn ràng buộc của ít nhất một subtask dưới đây.

Subtasks

• Subtask 1 ($30\%$ số test): $n\le 18$.
• Subtask 2 ($40\%$ số test): $n\le 80$, với mọi $i\ne j$ thì $A_i\ne B_j$ (tức là $x=0$).
• Subtask 3 ($30\%$ số test): $n\le 80$, $x\le 5$.

Ví dụ