#include<bits/stdc++.h> using namespace std; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } struct cell { int a,b,ind; }; bool cmp(cell a1,cell a2) { if(a1.a!=a2.a)return a1.a>a2.a; return a1.b<a2.b; } bool cmp2(cell a1,cell a2) { return a1.ind<a2.ind; } int n,k,a[100005],b[100005],br[200005],ind[200005],rr[200005],p[200005][20],ma; cell c[100005]; map<int,int>m,cur; void prec() { int to=1; c[0].b=ma+1; br[ma+1]=-1; for(int i=ma;i>=1;i--) { ind[i]=ind[i+1]; while(c[to].a==i) { //cout<<c[to].a<<" "<<c[to].b<<endl; if(c[to].b<c[ind[i]].b) { ind[i]=to; } to++; } rr[i]=c[ind[i]].b; br[i]=br[c[ind[i]].b]+1; p[i][0]=c[ind[c[ind[i]].b]].ind; //cout<<i<<" "<<br[i]<<endl; } sort(c+1,c+n+1,cmp2); for(int i=1;i<=18;i++) { for(int j=1;j<=ma;j++) { p[j][i]=p[c[p[j][i-1]].a][i-1]; } } /*for(int i=1;i<=ma;i++) { cout<<i<<" : "; for(int j=0;j<=3;j++) { cout<<p[i][j]<<" "; } cout<<endl; } cout<<endl; for(int i=1;i<=ma;i++) { cout<<br[i]<<" "; } cout<<endl;*/ } int get_st(int l,int r) { int to=l,br=0; for(int i=18;i>=0;i--) { if(c[p[to][i]].b<=r) { to=c[p[to][i]].a; br+=(1<<i); } } if(rr[to]<=r)br++; return br; } void resh() { cur[0]=1; cur[ma]=ma; int sum=br[1],st=0; if(br[1]<k) { cout<<-1<<endl; return; } for(int i=1;i<=n;i++) { auto l=cur.lower_bound(c[i].a); l=prev(l); auto r=cur.lower_bound(c[i].b); //cout<<l->second<<" "<<r->first<<endl; if(c[i].a<l->second||c[i].b>r->first)continue; st=sum-get_st(l->second,r->first); st=st+get_st(l->second,c[i].a)+get_st(c[i].b,r->first)+1; if(st>=k) { cout<<i<<endl; cur[c[i].a]=c[i].b; sum=st; } if(cur.size()==k+2)return; } } void read() { cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i]>>b[i]; m[a[i]]=1; m[b[i]]=1; } int dd=1; for(auto i=m.begin();i!=m.end();i++) { m[i->first]=dd; dd++; } ma=m.size(); //cout<<endl<<endl; for(int i=1;i<=n;i++) { a[i]=m[a[i]]; b[i]=m[b[i]]; c[i].a=a[i]; c[i].b=b[i]; c[i].ind=i; cout<<c[i].a<<" "<<c[i].b<<endl; } cout<<endl; sort(c+1,c+n+1,cmp); prec(); resh(); } int main() { speed(); read(); }