#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, q;
pair<int,int> z[1000005];
vector<int> v;
struct node {
int l, id;
};
const int INF = 1e16;
node f[4000005];
// Hàm combine: chọn nút có giá trị l nhỏ hơn; nếu bằng nhau thì chọn nút có id lớn hơn.
node combine(const node &left, const node &right) {
if (left.l < right.l) return left;
if (left.l == right.l && left.id > right.id) return left;
return right;
}
void build(int id, int l, int r) {
if (l == r) {
f[id] = {INF, INF};
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
f[id] = combine(f[id * 2], f[id * 2 + 1]);
}
void update(int id, int l, int r, int pos, int L, int idx) {
if (l == r) {
// Cập nhật nút tại vị trí pos với thông tin {L, idx}
f[id] = combine(f[id], {L, idx});
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
update(id * 2, l, mid, pos, L, idx);
else
update(id * 2 + 1, mid + 1, r, pos, L, idx);
f[id] = combine(f[id * 2], f[id * 2 + 1]);
}
node query(int id, int l, int r, int ql, int qr) {
if (qr < l || ql > r)
return {INF, INF};
if (ql <= l && r <= qr)
return f[id];
int mid = (l + r) / 2;
node leftNode = query(id * 2, l, mid, ql, qr);
node rightNode = query(id * 2 + 1, mid + 1, r, ql, qr);
return combine(leftNode, rightNode);
}
int up[100005][25];
int cost[100005][25];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> q;
for (int i = 1; i <= a; i++) {
cin >> z[i].first >> z[i].second;
v.push_back(z[i].first);
v.push_back(z[i].second);
}
// Tiến hành coordinate compression
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int n = v.size();
for (int i = 1; i <= a; i++) {
z[i].first = lower_bound(v.begin(), v.end(), z[i].first) - v.begin() + 1;
z[i].second = lower_bound(v.begin(), v.end(), z[i].second) - v.begin() + 1;
}
// Xây dựng cây phân đoạn trên khoảng [1, n]
build(1, 1, n);
// Với mỗi khoảng, cập nhật tại vị trí = z[i].second giá trị là {z[i].first, i}
for (int i = 1; i <= a; i++) {
update(1, 1, n, z[i].second, z[i].first, i);
}
// Xây dựng bảng nhảy một bước (up[i][0]) và chi phí tương ứng.
// Với mỗi khoảng i, truy vấn trên [z[i].first, z[i].second] để tìm khoảng "tối ưu" nối được với i.
for (int i = 1; i <= a; i++) {
node res = query(1, 1, n, z[i].first, z[i].second);
// Nếu không tìm được khoảng nào khác (res.id == i) thì không có bước nhảy
if (res.id == i) {
up[i][0] = i;
cost[i][0] = 0;
} else {
up[i][0] = res.id;
cost[i][0] = 1;
}
}
// Xây dựng bảng nhảy đôi (binary lifting)
for (int j = 1; j <= 20; j++) {
for (int i = 1; i <= a; i++) {
up[i][j] = up[up[i][j - 1]][j - 1];
cost[i][j] = cost[i][j - 1] + cost[up[i][j - 1]][j - 1];
}
}
// Xử lý truy vấn:
// Mục tiêu: từ khoảng x có thể nối chuỗi tới khoảng y với số bước tối thiểu
while (q--) {
int x, y;
cin >> x >> y;
if (x == y) {
cout << 0 << "\n";
continue;
}
// Nếu khoảng bắt đầu của x không nhỏ hơn kết thúc của y, không nối được
if (z[x].first >= z[y].second) {
cout << "impossible" << "\n";
continue;
}
int p = y;
int ans = 0;
// Sử dụng nhảy nhị phân từ y về x (tìm khoảng mà z[x].second có thể nối được)
for (int i = 20; i >= 0; i--) {
int candidate = up[p][i];
// Nếu khoảng candidate vẫn có đầu trái lớn hơn z[x].second, ta có thể nhảy ngược tiếp
if (z[candidate].first > z[x].second) {
ans += cost[p][i];
p = candidate;
}
}
// Kiểm tra sau nhảy nhị phân, nếu z[x].second nối được với khoảng p thì cộng thêm 1 bước
if (z[x].second >= z[p].first) {
cout << ans + 1 << "\n";
} else {
// Thử nhảy thêm một bước nữa
p = up[p][0];
if (z[x].second >= z[p].first) {
cout << ans + 2 << "\n";
} else {
cout << "impossible" << "\n";
}
}
}
return 0;
}
