Cho n đoạn trên trục số, đoạn thứ i là [Li, Ri].
Hãy chọn ra trong các đoạn kể trên một số ít nhất các đoạn để phủ hết đoạn [a, b]
Dữ liệu: Vào từ file văn bản COVER.INP
- Dòng 1: Chứa 3 số n, a, b
- n dòng tiếp theo, dòng thứ i chứa hai số Li và Ri
Kết quả: Ghi ra file văn bản COVER.OUT
- Dòng 1: Ghi số k là số đoạn được chọn (Nếu không có cách chọn thì k = -1)
- Trong trường hợp có phương án thực hiện yêu cầu thì k dòng tiếp theo, mỗi dòng ghi chỉ số một đoạn được chọn
Các số trên một dòng của Input/Output file cách nhau ít nhất một dấu cách
Ràng buộc: 1 \(<=\) n <=</strong> 100000; các số còn lại là số nguyên dương <=</strong> 30000; a <=</strong> b; \(\forall\)i: Li <=</strong> Ri
Ví dụ:
|
COVER.INP
|
COVER.OUT
|
|
COVER.INP
|
COVER.OUT
|
|
8 2 10
4 8
1 3
2 3
1 4
3 4
7 10
9 11
8 11
|
3
1
4
6
|
|
8 1 200
1 4
2 5
4 5
6 45
6 7
5 7
100 200
50 99
|
-1
|
trannhat900 
phamngoctienpy1987844 
vxh2k9850 
Nqoc_baka 