## Subtask 1
Để ý giới hạn $n \leq 20$, vì mỗi đoạn thẳng ta chỉ có lựa chọn là chọn/không chọn, ta back_track $2^n$ trạng thái, mỗi đoạn thẳng có hai trạng thái là $0/1$ tương ứng với việc chọn / không chọn.

Sau khi đã có được trạng thái các đoạn thẳng, ta kiểm tra xem liệu đoạn từ $x$ tới $y$ có được bao phủ bởi tất cả các đoạn thẳng hay không. Khi ta có $1$ tập các đoạn thẳng được chọn, để xem liệu đoạn từ $x$ tới $y$ có được bao phủ hoàn toàn không, ta sort các đoạn lại tăng dần theo $l$, điều kiện giữa hai đoạn liên tiếp là $r_1 \geq l_2$ (tức hai đoạn phải giao nhau, nếu không sẽ có ít nhất một điểm không nguyên không được bao phủ).

Vì vậy, ta lựa chọn sort các đoạn tăng dần theo $l$ trước, và khi back_track chỉ cần duy trì đầu mút $r$ hiện tại.

ĐPT: O($2^n \times q$).
## Subtask 2

Nhận xét tham lam quan trọng: ta sẽ thêm dần các đoạn thẳng vào sao cho đoạn bao phủ của ta mở rộng dần từ trái qua phải, bắt đầu từ $x$ cho đến khi bao phủ hết $y$. Khi đó, nếu đầu mút bên phải phần bao phủ hiện tại của ta là $pos$, ta sẽ lựa chọn đoạn $l$, $r$ để nối thêm vào sao cho $l \leq pos$ và $r$ max, vì khi đó đoạn của ta sẽ được mở rộng nhiều nhất.

Gọi $nxt[pos]$ là vị trí xa nhất ta nhảy đến được nếu đầu mút phải hiện tại đang là $pos$, ta đi tính mảng $nxt$ bằng cách sau:

* B1: Với mọi đoạn $l, r$ nhập vào, ta gán $nxt[l]$ = max($nxt[l]$, $r$).
* B2: Với mọi $i$ từ $1$ đến $1e5$, ta gán $nxt[i]$ = max($nxt[i]$, $nxt[i-1]$, $i$).

Vận dụng mảng $nxt$, ta tính đáp án như sau:

Ban đầu gán $pos = x$, sau đó với mỗi đoạn dùng thêm bằng cách tham lam ở trên, ta sẽ đến được vị trí $nxt[pos]$, ta dùng mảng $nxt[pos]$ để nhảy từng bước đến khi tới được $y$.

int res = 0;
while(x != y)
{
    if(x == nxt[x])
    {
        res = -1;
        break;
    }
    x = nxt[x];
    ++res;
}

## Subtask 3

Nhận thấy mảng $nxt$ là cố định, ta vận dũng sparse table để nhảy trên mảng $nxt$ $2^i$ bước một lần thay vì từng bước (khá giống lca, đây là dạng toán dùng sparse table để nhảy).

Ta xây dựng mảng $nxt[i][j]$ là vị trí mà $i$ tới được, sau khi dùng $2^j$ đoạn.

$nxt[i][0]$ là mảng $nxt$ ở subtask 2.
$nxt[i][j]$ = $nxt[nxt[i][j-1]][j-1]$.

Sau đó ta vận dụng sparse table để tính đáp án như sau:

int res = 0;
for(int i = log2(1e5); i >= 0; --i)
{
    if(nxt[x][i] <= y && (i == 0 || nxt[x][i] != nxt[x][i-1]))
    {
        res += (1<<i);
        x = nxt[x][i];
    }
}
if(x < y)
    x = nxt[x][0], ++res;
if(x < y)
    res = -1;

Lí do phải kiểm tra $nxt[x][i] \neq nxt[x][i-1]$ là vì nếu không có đoạn nào đi qua $pos$, $nxt[pos]$ sẽ bằng $pos$ và ta sẽ dậm chân tại chỗ.