# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1125024 | EfeBabagil | Event Hopping (BOI22_events) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
int n,qu;
cin>>n>>qu;
vector<array<int,3>> events(n);
for(int i=0;i<n;i++)
{
int e,s;
cin>>s>>e;
events[i]={s,e,i};
}
while(qu--)
{
int a,b;
cin>>a>>b;
a--;
b--;
vector<int> dis(n+1,-1);
dis[a]=0;
queue<int> q;
q.push(a);
if(a==b){
cout<<"0"<<endl;
continue
}
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<n;i++)
{
if(dis[i]!=-1)
continue;
if(events[i][0] <= events[x][1] && events[x][1] <= events[i][1]) {
dis[i] = dis[x] + 1;
q.push(i);
}
}
}
if(dis[b] == -1)
cout<<"impossible"<<endl;
else
cout<<dis[b]<<endl;
}
return 0;
}