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:
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.
Kết quả:
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:
2 2 2 3
1 2
1 3
3 7
Kết quả:
4
1 5
2 6
3 4
7 8
Giới hạn:
Subtask #1: số điểm có ;
Subtask #2: số điểm khác có ;
Subtask #3: số điểm còn lại không có ràng buộc bổ sung.
