Chỉnh Sửa Tình Bạn

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có $N$ con bò với các mối quan hệ bạn bè được biểu diễn bởi đồ thị vô hướng gồm $M$ cạnh.

Trong một thao tác, bạn có thể thêm hoặc xóa một cạnh bất kỳ. Hãy tìm số thao tác tối thiểu để đồ thị thỏa mãn tính chất sau:

Nếu bò $a$ và bò $b$ là bạn, thì với mọi bò $c$ khác, ít nhất một trong hai bò $a$ hoặc $b$ phải là bạn của $c$ .

Nói cách khác, với mọi cạnh $(a, b)$ trong đồ thị, tập hàng xóm chung của $a$ và $b$ phải phủ hết tất cả các đỉnh còn lại.

Dòng 1: Hai số nguyên $N$ và $M$ ( $2 \leq N \leq 16$ , $0 \leq M \leq N (N - 1) / 2$ )
$M$ dòng tiếp theo: Hai số $a$ và $b$ ( $1 \leq a < b \leq N$ ) biểu diễn cặp bạn bè

In ra số thao tác tối thiểu.

Input	Output	Giải thích
3 1 1 2	1	Thêm cạnh $(2, 3)$ hoặc $(1, 3)$ , hoặc xóa $(1, 2)$ .
3 2 1 2 2 3	0	Đã thỏa mãn: với cạnh $(1, 2)$ thì 2 là bạn của 3; với cạnh $(2, 3)$ thì 2 là bạn của 1.
4 4 1 2 1 3 1 4 2 3	1	Cạnh $(2, 3)$ vi phạm vì cả 2 và 3 đều không là bạn của 4. Thêm cạnh $(2, 4)$ hoặc $(3, 4)$ là đủ.

Bình luận

Không có bình luận tại thời điểm này.