#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=(int)1e5;
const int INF=(int)1e9;
int s[N+2],e[N+2],l[N+2],r[N+2];
int n,q,limit_size;
vector<int>pp;
vector<int>nen;
class Segment_tree{
public:
vector<int>st;
void init(int _n){
st.assign(_n*4+2,INF);
return;
}
void upd(int id,int l,int r,int pos,int val){
if (l>pos||r<pos) return;
if (l==r) st[id]=min(st[id],val);
else {
int m=(l+r)/2;
upd(id*2,l,m,pos,val);
upd(id*2+1,m+1,r,pos,val);
st[id]=min(st[id*2],st[id*2+1]);
}
return;
}
int Get(int id,int l,int r,int u,int v){
if (l>v||r<u) return INF;
if (u<=l&&r<=v) return st[id];
int m=(l+r)/2;
return min(Get(id*2,l,m,u,v),Get(id*2+1,m+1,r,u,v));
}
};
Segment_tree st;
int Find(int x){
return upper_bound(nen.begin(),nen.end(),x)-nen.begin();
}
namespace subtask1{
bool check(){
return n<=5000;
}
const int LIMIT_SIZE=3000;
int f[LIMIT_SIZE+2][LIMIT_SIZE+2];
void process(int x){
st.init(limit_size);
st.upd(1,1,limit_size,e[x],0);
f[x][x]=0;
for(auto&id:pp){
int val=st.Get(1,1,limit_size,s[id],e[id])+1;
st.upd(1,1,limit_size,e[id],val);
if (id==x) continue;
f[x][id]=val;
}
return;
}
void main_code(){
for(int i=1;i<=n;++i) process(i);
for(int i=1;i<=q;++i) {
int val=f[l[i]][r[i]];
if (val>=INF) cout<<"impossible\n";
else cout<<val<<'\n';
}
return;
}
}
namespace subtask2{
bool check(){
return q<=1000;
}
int process(int x,int target){
if (x==target) return 0;
st.init(limit_size);
st.upd(1,1,limit_size,e[x],0);
for(auto&id:pp){
int val=st.Get(1,1,limit_size,s[id],e[id])+1;
st.upd(1,1,limit_size,e[id],val);
if (id==target) return val;
}
return INF;
}
void main_code(){
for(int i=1;i<=q;++i) {
int k=process(l[i],r[i]);
if (k>=INF) cout<<"impossible\n";
else cout<<k<<'\n';
}
return;
}
}
namespace subtask3{
bool check(){
return true;
}
const int MAXLOG=(int)17;
int par[N+2][MAXLOG+2];
int id[N+2];
int binary_jump(int x,int target){
if (id[x]>id[target]) return INF;
if (id[target]==id[x]) return 0;
x=id[x];
int ans=0;
for(int i=MAXLOG;i>=0;--i){
if (par[x][i]<id[target]){
ans+=(1<<i);
x=par[x][i];
}
}
for(int i=0;i<=MAXLOG;++i){
if (par[x][i]>=id[target]){
return ans+(1<<i);
}
}
return INF;
}
void main_code(){
for(int i=0,j=0;i<pp.size();++i){
while (j<pp.size() && s[pp[j]]<=e[pp[i]] && e[pp[i]]<=e[pp[j]]) ++j;
par[i][0]=j-1;
id[pp[i]]=i;
}
for(int j=1;j<=MAXLOG;++j){
for(int i=0;i<n;++i){
par[i][j]=par[par[i][j-1]][j-1];
}
}
for(auto&x:pp) cout<<x<<' '; cout<<'\n';
for(int i=0;i<n;++i) cout<<par[i][0]<<'\n';
for(int i=1;i<=q;++i){
int k=binary_jump(l[i],r[i]);
if (k>=INF) cout<<"impossible\n";
else cout<<k<<'\n';
}
return;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
#define task "main"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>s[i]>>e[i];
for(int i=1;i<=q;++i) cin>>l[i]>>r[i];
for(int i=1;i<=n;++i) {
nen.push_back(s[i]);
nen.push_back(e[i]);
}
sort(nen.begin(),nen.end());
nen.resize(unique(nen.begin(),nen.end())-nen.begin());
limit_size=nen.size();
for(int i=1;i<=n;++i){
s[i]=Find(s[i]) , e[i]=Find(e[i]);
pp.push_back(i);
}
sort(pp.begin(),pp.end(),[&](int x,int y){
if (s[x]!=s[y]) return s[x]<s[y];
return e[x]<e[y];
});
if (subtask2::check()) return subtask2::main_code(),0;
// if (subtask1::check()) return subtask1::main_code(),0;
if (subtask3::check()) return subtask3::main_code(),0;
return 0;
}
