THỰC HÀNH

Xét hình hộp chữ nhật kích thước a × b × c. Hình hộp có c tầng, các tầng được đánh số từ 1 đến c; trên mỗi tầng, có a hàng, các hàng được đánh số từ 1 đến a; trên mỗi hàng, có b khoảng, các khoảng được đánh số từ 1 đến b. Ô nằm ở khoảng j trên hàng thứ i của tầng k được đánh số (k − 1) × a × b + (i − 1) × b + j.

Nhiệm vụ của bạn là xếp được càng nhiều thanh DOM có kích thước 1 × 1 × 2 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 a, b, c và s (s ≤ a × b × c ≤ 10000);
• Tiếp theo là s dòng, mỗi dòng chứa hai số nguyên pᵢ, qᵢ là hai ô kề cạnh được đánh số là pᵢ, qᵢ mà giữa hai ô có vách ngăn.

Dữ liệu ra:

• Dòng đầu chứa số nguyên r là số lượng thanh DOM đặt được trong hình hộp;
• Tiếp theo là r dòng, mỗi dòng chứa hai số nguyên uᵢ, vᵢ là hai ô kề cạnh được đánh số là uᵢ, vᵢ 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 0 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á 10% thanh DOM.
• Ngược lại, điểm của bạn được tính bằng: 1000 × (q/p − 0.9) trong đó p, q 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.