Nguồn: Ôn HN tháng 11/2016, Thầy Nguyễn Đức Nghĩa, Ngày 1
Bộ bài domino gồm những thanh hình chữ nhật, mỗi thanh được chia ra thành hai hình vuông bằng nhau. Trên mỗi nửa quân bài người ta ghi các số từ đến . Một bộ bài domino đủ như vậy sẽ có tất cả các cặp hai số nguyên khác nhau. Ví dụ, nếu , bộ bài đủ sẽ bao gồm quân bài .
Ta có thể nối các quân bài domino lại thành một dãy bằng cách gộp theo cạnh ngắn của hai quân bài với điều kiện hai ô vuông có cạnh tiếp xúc ở hai quân bài có giá trị số ghi trên chúng là như nhau.
Yêu cầu: Cho tập gồm một số quân bài của bộ bài domino . Cần tìm cách gộp các quân bài đã cho thành một số ít nhất dãy có thể được sao cho mỗi quân bài phải thuộc vào đúng một trong các dãy xây dựng.
Dữ liệu vào:
Dòng đầu tiên ghi số nguyên dương - giá trị số lớn nhất trên một nửa của quân bài domino;
Dòng thứ hai ghi số nguyên là số lượng quân bài bị loại khỏi bộ bài;
Dòng thứ trong số dòng tiếp theo ghi hai số nguyên cách nhau bởi dấu cách là cặp giá trị số viết trên quân bài thứ trong số quân bài bị loại khỏi bộ bài.
Dữ liệu ra:
Ghi ra số lượng dãy ít nhất gộp được từ các quân bài còn lại sao cho mỗi quân bài còn lại phải thuộc vào đúng một dãy.
