#826. SBBCFFFFS - Leo núi

Đất nước Thụy Sỹ nổi tiếng với những ngọn núi cao ngất và những hồ nước xanh trong vắt. Nơi đây không có những thành phố sầm uất như London, Paris hay những công trình nổi tiếng để thu hút khách du lịch. Thụy Sỹ lôi cuốn bởi vẻ đẹp hoang dã mà thiên nhiên ban tặng. Du khách năm châu tới đây chủ yếu để leo lên những đỉnh núi cao ngất như Rigi, Pilatus hay Alps; chiêm ngưỡng cảnh thiên nhiên hùng vĩ và thu trọn cả đất nước Thụy Sỹ vào tầm mắt.

Trong kỳ thực tập tại Google Zurich, GSPVH lên kế hoạch chinh phục hết các ngọn núi tại đây. Đất nước Thụy Sỹ có ngọn núi, chia vào khu vực. khu vực này có thể giao nhau, vì thế một ngọn núi có thể thuộc về nhiều hơn một khu vực. Nói cách khác, mỗi khu vực là một tập con của tập hợp ngọn núi. Để thuận tiện, các ngọn núi được đánh số từ tới , và ta sẽ coi như có khu vực, đánh số từ tới . Các khu vực từ tới chỉ có một ngọn núi (khu vực bao gồm ngọn núi ), các khu vực từ tới có ít nhất hai ngọn núi.

Trước khi lên lịch khám phá ngọn núi, GSPVH thu thập thông tin về độ hiểm trở của chúng thông qua những thực tập sinh khác. Theo đó, độ hiểm trở của mỗi ngọn núi thuộc một trong mức, đánh số từ tới và không có hai ngọn núi nào có cùng độ hiểm trở. Ngoài ra, những người bạn của GSPVH còn cung cấp mẩu thông tin, thuộc một trong bốn dạng sau:

1. với , cho biết trong khu vực , ngọn núi có độ hiểm trở lớn nhất;
2. với , cho biết trong khu vực , ngọn núi có độ hiểm trở nhỏ nhất;
3. với , cho biết mọi ngọn núi ở khu vực có độ hiểm trở không lớn hơn mọi ngọn núi ở khu vực ;
4. với , cho biết mọi ngọn núi ở khu vực có độ hiểm trở không nhỏ hơn mọi ngọn núi ở khu vực .

GSPVH muốn chinh phục các đỉnh núi với độ hiểm trở tăng dần. Vì vậy các bạn hãy sắp xếp các ngọn núi theo thứ tự này nhé. Do thông tin thu thập được còn ít, có thể có nhiều thứ tự cùng thỏa mãn. Trong trường hợp đó, bạn nên đưa ra dãy có thứ tự từ điển nhỏ nhất. Dữ liệu vào đảm bảo có ít nhất một thứ tự hợp lệ.

Dữ liệu vào:

• Dòng thứ nhất chứa ba số nguyên dương , và - số ngọn núi, số khu vực và số mẩu thông tin GSPVH thu được;
• dòng tiếp theo, dòng thứ gồm hai số và ; thể hiện tập hợp các ngọn núi thuộc khu vực là hợp của tập hợp các ngọn núi thuộc khu vực và khu vực ;
• dòng tiếp theo, mỗi dòng thể hiện một mẩu thông tin theo một trong bốn dạng nêu trên.

Dữ liệu ra:

• Gồm một dòng duy nhất chứa số, lần lượt là số thứ tự của các ngọn núi theo thứ tự độ hiểm trở tăng dần.

Giới hạn:

Với mỗi test, bạn sẽ nhận được

• số điểm nếu đáp án của bạn thoả mãn tất cả 𝒎 mẩu thông tin và có thứ tự từ điển nhỏ nhất, hoặc
• số điểm nếu đáp án của bạn thoả mãn thất cả mẩu thông tin, hoặc
• số điểm nếu đáp án của bạn thoả mãn tất cả các mẩu thông tin loại và hoặc với , hoặc
• số điểm nếu đáp án của bạn là hoán vị của các số tự nhiên từ tới , hoặc
• điểm trong các trường hợp còn lại.

Ví dụ:

Dữ liệu vào:

7 5 4
2 4
8 1
3 6
7 3
10 11
12 > 9
MIN 8 4
MAX 12 6
11 < 10

Dữ liệu ra:

1 4 2 5 7 3 6

Dữ liệu vào:

4 1 2
1 2
1 > 2
5 > 3

Dữ liệu ra:

4 1 2 3

Hoặc một trong các thứ tự sau:

4 2 1 3
4 3 2 1
3 2 1 4

Giải thích:

Trong ví dụ đầu tiên:

• Có ngọn núi và khu vực.
• Khu vực có ngọn núi , khu vực có ngọn núi ,…, khu vực có ngọn núi .
• Khu vực có các ngọn núi và .
• Khu vực có các ngọn núi và .
• Khu vực có các ngọn núi và .
• Khu vực có các ngọn núi và .
• Khu vực có các ngọn núi và . Trong ví dụ thứ hai: dữ liệu ra mẫu, từ trên xuống dưới, lần lượt cho số điểm, số điểm, số điểm và số điểm.