#include <bits/stdc++.h>

using namespace std;

class nameclass{
    public:
        bool operator()(int &a, int &b){
            return a>b;
        }
};

struct scale{
    int f;
    int s;
    int t;
};

vector<scale> g[1000000];
long long int dist[10000000];
priority_queue<int, vector<int>, nameclass> pq;
scale P;

void Dijkstra(){
    pq.push(0);
    dist[0]=0;
    while(!pq.empty()){
        int h=pq.top();
        pq.pop();
        for(int x=0; x<g[h].size(); x++){
            if(g[h][x].s<=dist[h] && g[h][x].t>=dist[h]+1){
                if(dist[g[h][x].f]==-1 || dist[h]+1<dist[g[h][x].f]){
                    dist[g[h][x].f]=dist[h]+1;
                    pq.push(g[h][x].f);
                    continue;
                }
            }
            if(g[h][x].s>dist[h]){
                if(dist[g[h][x].f]==-1 || g[h][x].s+1<dist[g[h][x].f]){
                    dist[g[h][x].f]=g[h][x].s+1;
                    pq.push(g[h][x].f);
                }
            }
        }
    }
}

int raggiungi(int N, int M, int A[], int B[], int inizio[], int fine[]) {
    for(int x=0; x<M; x++){
        P.f=B[x];
        P.s=inizio[x];
        P.t=fine[x];
        g[A[x]].push_back(P);
        P.f=A[x];
        P.s=inizio[x];
        P.t=fine[x];
        g[B[x]].push_back(P);
    }
    for(int x=0; x<N; x++){
        dist[x]=-1;
    }
    Dijkstra();
    return dist[N-1];
}