Xét hình hộp chữ nhật kích thước . Hình hộp có tầng, các tầng được đánh số từ đến ; trên mỗi tầng, có hàng, các hàng được đánh số từ đến ; trên mỗi hàng, có khoảng, các khoảng được đánh số từ đến . Ô nằm ở khoảng trên hàng thứ của tầng được đánh số .
Nhiệm vụ của bạn là xếp được càng nhiều thanh DOM có kích thước vào hình hộp, biết rằng giữa một số cặp ô chung cạnh có vách ngăn, do đó không thể đặt một thanh DOM vào hai ô này được.
Dữ liệu vào:
Dòng đầu chứa bốn số nguyên và ;
Tiếp theo là dòng, mỗi dòng chứa hai số nguyên là hai ô kề cạnh được đánh số là mà giữa hai ô có vách ngăn.
Dữ liệu ra:
Dòng đầu chứa số nguyên là số lượng thanh DOM đặt được trong hình hộp;
Tiếp theo là dòng, mỗi dòng chứa hai số nguyên là hai ô kề cạnh được đánh số là sẽ được đặt thanh DOM mà giữa hai ô đó không có vách ngăn.
Ví dụ:
Dữ liệu vào:
2 2 2 3
1 2
1 3
3 7
Dữ liệu ra:
4
1 5
2 6
3 4
7 8
Cách chấm điểm:
Bạn sẽ bị điểm nếu đặt sai hoặc số lượng thanh DOM đặt được ít hơn số lượng thanh đặt được trong phương án tối ưu quá thanh DOM.
Ngược lại, điểm của bạn được tính bằng: trong đó tương ứng là số lượng thanh DOM đặt được trong phương án tối ưu và trong phương án của bạn.
