#include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll INF = 1e+15; typedef pair P; struct edge{ int to; ll cost; }; vector G[100005]; ll d[100005]; void dijkstra(int s, int num_v){ priority_queue, greater

> que; fill(d, d+num_v, INF); d[s] = 0; que.push(P(0, s)); while(!que.empty()){ P p = que.top();que.pop(); int v = p.second; if(d[v] < p.first) continue; for(int i = 0; i < G[v].size(); i++){ edge e = G[v][i]; if(d[v] + e.cost < d[e.to]){ d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } int N, M, A, B; int L[100005], R[100005]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> N >> M >> A >> B; A--;// B--; for(int i = 0; i < M; i++){ cin >> L[i] >> R[i]; L[i]--; R[i]--; } for(int i = 0; i < A; i++){ G[i].push_back((edge){i+1, 0}); } for(int i = B; i < N; i++){ G[i].push_back((edge){i+1, 0}); } for(int i = 0; i < M; i++){ G[L[i]].push_back((edge){R[i]+1, 1}); G[R[i]+1].push_back((edge){L[i], 1}); } dijkstra(0, N+1); // for(int i = 0; i <= N; i++) cout << d[i] << ' '; // cout << endl; if(d[N] == INF){ cout << -1 << endl; return 0; } cout << d[N] << endl; }