\(N\) con bò của Farmer John được đánh số từ \(1\) đến \(N\) (\(2\le N\le 16\)). Quan hệ bạn bè giữa các con bò có thể được mô hình hóa bằng một đồ thị vô hướng có \(M\) (\(0\le M\le N(N-1)/2\)) cạnh. Hai con bò là bạn bè khi và chỉ khi có một cạnh nối chúng trong đồ thị.

Trong một thao tác, bạn có thể thêm hoặc xóa một cạnh khỏi đồ thị. Hãy tính số thao tác tối thiểu cần thiết để đảm bảo tính chất sau: nếu hai con bò \(a\) và \(b\) là bạn bè, thì với mọi con bò khác \(c\), ít nhất một trong hai con \(a\) và \(b\) là bạn bè với \(c\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\).

\(M\) dòng tiếp theo, mỗi dòng chứa một cặp bạn bè \(a\) và \(b\) (\(1\le a<b\le N\)). Không có cặp bạn bè nào xuất hiện quá một lần.

Dữ liệu ra

In ra số cạnh cần thêm hoặc xóa.

Ví dụ

3 1
1 2

1

3 2
1 2
2 3

0

4 4
1 2
1 3
1 4
2 3

1

Phân nhóm

• Dữ liệu 4–13: Có một test cho mỗi \(N\in[6,15]\), theo thứ tự tăng dần.
• Dữ liệu 14–18: \(N=16\).

Nguồn

USACO 2025 February Contest, Gold — Friendship Editing. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1499