#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int base=1<<13; int inf=1e9+50; vector<pair<int, int>> T(2*base, {inf,0}); pair<int,int> query(int a, int b) { if(a>b) return {inf,0}; if(a==b) return T[a+base]; a+=base-1; b+=base+1; pair<int, int> ans = {inf,0}; while(a/2!=b/2) { if(a%2==0) ans = min(ans, T[a+1]); if(b%2==1) ans = min(ans, T[b-1]); a/=2; b/=2; } return ans; } void update(int x, pair<int, int> val) { x += base; T[x] = val; x/=2; while(x>0) { T[x] = min(T[x+x], T[x+x+1]); x/=2; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; vector<vector<int>> ans(n, vector<int>(n, inf)); vector<pair<pair<int, int>, int>> seg(n); vector<int> left(n), right(n), pozycja(n); vector<int> Y; for(int i=0; i<n; ++i) { cin >> left[i] >> right[i]; seg[i].first = {right[i], left[i]}; seg[i].second = i; } sort(seg.begin(), seg.end()); for(int i=0; i<n; ++i) { pozycja[seg[i].second] = i; } auto check = [&](int v, int j) { return (left[j] <= right[v] && right[v] <= right[j]); }; queue<int> Q; for(int s=0; s<n; ++s) { //epic T.assign(2*base, {inf,0}); for(int i=0; i<n; ++i) { update(i, {seg[i].first.second, seg[i].second}); } ans[s][s] = 0; Q.push(s); while(Q.size()) { int v = Q.front(); Q.pop(); int poz = lower_bound(Y.begin(), Y.end(), left[v]) - Y.begin(); while(1) { auto[val, j] = query(poz, base-1); // cout << v << ": " << val << " " << j << " - " << right[v] << "\n"; if(val > right[v]) break; update(pozycja[j], {inf,j}); if(check(v,j) && ans[s][j] == inf) { ans[s][j] = ans[s][v] + 1; Q.push(j); } } } } while(q--) { int a, b; cin >> a >> b; --a;--b; if(ans[a][b]==inf) cout << "impossible\n"; else cout << ans[a][b] << "\n"; } return 0; }