#include <iostream> #include <algorithm> #include <vector> #include <map> #define endl '\n' using namespace std; const int MAXN = 1e5 + 10; const int MAXLOG = 20; const int INF = 1e9 + 10; int n, q; map < int, int > mp; pair < int, int > st[MAXN][MAXLOG]; int jump[MAXN][MAXLOG]; int lg[MAXN]; int l[MAXN]; int r[MAXN]; void read() { cin >> n >> q; for(int i = 1; i <= n; i++) { cin >> l[i] >> r[i]; } } pair < int, int > minquery(int left, int right) { int len = right - left + 1; int k = lg[len]; return min(st[left][k], st[right - (1 << k) + 1][k]); } void precomp() { vector < int > rs; for(int i = 1; i <= n; i++) { rs.push_back(r[i]); } sort(rs.begin(), rs.end()); rs.erase(unique(rs.begin(), rs.end()), rs.end()); int sz = rs.size(); for(int i = 0; i < sz; i++) { mp[rs[i]] = i; } for(int j = 0; j < MAXLOG; j++) { for(int i = 0; i <= n; i++) { st[i][j] = {INF, INF}; } } for(int i = 1; i <= n; i++) { st[mp[r[i]]][0] = min(st[mp[r[i]]][0], {l[i], i}); } for(int i = 2; i <= n; i++) { lg[i] = lg[i / 2] + 1; } for(int j = 1; (1 << j) <= n; j++) { for(int i = 0; i + (1 << j) - 1 <= n; i++) { st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } } for(int i = 1; i <= n; i++) { int from = lower_bound(rs.begin(), rs.end(), l[i]) - rs.begin(); int to = mp[r[i]]; jump[i][0] = minquery(from, to).second; } for(int j = 1; (1 << j) <= n; j++) { for(int i = 1; i + (1 << j) - 1 <= n; i++) { jump[i][j] = jump[jump[i][j - 1]][j - 1]; } } } int query(int x, int y) { if(x == y) return 0; if(l[y] <= r[x] && r[x] <= r[y]) return 1; int ans = 1; for(int j = MAXLOG - 1; j >= 0; j--) { if(r[x] < l[jump[y][j]]) { ans += (1 << j); y = jump[y][j]; } } y = jump[y][0]; if(r[x] < l[y] || r[x] > r[y]) return -1; if(r[x] >= l[y]) ans++; return ans; } void process_queries() { for(int i = 1; i <= q; i++) { int x, y; cin >> x >> y; int ans = query(x, y); if(ans == -1) { cout << "impossible" << endl; } else { cout << ans << endl; } } } int main() { /* ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);*/ read(); precomp(); process_queries(); return 0; }