Iahub got lost in a very big desert. The desert can be represented as a *n* × *n* square matrix, where each cell is a zone of the desert. The cell (*i*, *j*) represents the cell at row *i* and column *j* (1 ≤ *i*, *j* ≤ *n*). Iahub can go from one cell (*i*, *j*) only down or right, that is to cells (*i* + 1, *j*) or (*i*, *j* + 1). 

Also, there are *m* cells that are occupied by volcanoes, which Iahub cannot enter. 

Iahub is initially at cell (1, 1) and he needs to travel to cell (*n*, *n*). Knowing that Iahub needs 1 second to travel from one cell to another, find the minimum time in which he can arrive in cell (*n*, *n*).
The first line contains two integers *n* (1 ≤ *n* ≤ 10<sup class="upper-index">9</sup>) and *m* (1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>). Each of the next *m* lines contains a pair of integers, *x* and *y* (1 ≤ *x*, *y* ≤ *n*), representing the coordinates of the volcanoes.

Consider matrix rows are numbered from 1 to *n* from top to bottom, and matrix columns are numbered from 1 to *n* from left to right. There is no volcano in cell (1, 1). No two volcanoes occupy the same location.
#include <iostream>
#include <vector>
#include <queue>
#define MAX_tam 1000000000
using namespace std;
typedef unsigned long long int llu;


typedef struct{
    llu x,y;
}point;

typedef struct{
    vector<int> path;
    int total=0;
}fila;


typedef struct{
    point ponto;
    int dist;
}queuenode;



bool isValid(llu n, llu x, llu y){
    return (x>=0) && (y>0) && (x<n) && (y<n);
}

// function to find the shortest path between
// a given source cell to a destination cell.
int BFS(llu n,int **mat,bool **visited, llu srcx, llu srcy, llu destx, llu desty)
{


    visited[srcx][srcy] = true;
    point src={ srcx,srcy};
    queue<queuenode> fila_visita;
    // Enqueue sour
    // Do a BFS starting from source cell
    while (fila_visita.empty())
    {
        queuenode curr = fila_visita.front();
        point pt = curr.ponto;

        // If we have reached the destination cell,
        // we are done
        if (pt.x == destx && pt.y == desty)
            return curr.dist;

        // Otherwise dequeue the front cell in the queue
        // and enqueue its adjacent cells
        fila_visita.pop();


            point left={pt.x+1, pt.y};
            point down={pt.x,pt.y+1};
            // if adjacent cell is valid, has path and
            // not visited yet, enqueue it.
            if (isValid(n,left.x, left.y) && mat[left.x][left.y] &&
                !visited[left.x][left.y])
            {
                // mark cell as visited and enqueue it
                visited[left.x][left.y] = true;
                queuenode Adjcell = { left, curr.dist + 1 };
                fila_visita.push(Adjcell);
            }

        // if adjacent cell is valid, has path and
        // not visited yet, enqueue it.
        if (isValid(n,down.x, down.y) && mat[down.x][down.y] &&
            !visited[down.x][down.y])
        {
            // mark cell as visited and enqueue it
            visited[down.x][down.y] = true;
            queuenode Adjcell = { down, curr.dist + 1 };
            fila_visita.push(Adjcell);
        }
    }

    // Return -1 if destination cannot be reached
    return -1;
}


int main() {
    llu m,n, cordx, cordy;
    long long int resp=-1;
    cin >> n >> m;
    int matrix[n][n];
    bool visited[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            matrix[i][j]=1;
            visited[i][j]=false;
        }
    }

    for(int i=0;i<m;i++){
        cin >> cordx >> cordy;
        matrix[cordx-1][cordy-1]=0;
        visited[cordx-1][cordy-1]=true;
    }

    visited[0][0] = true;
    point src={ 0,0};
    queue<queuenode> fila_visita;
    queuenode temp={src, 0};
    fila_visita.push(temp);
    // Enqueue sour
    // Do a BFS starting from source cell
    while (!fila_visita.empty())
    {
        queuenode curr = fila_visita.front();
        point pt = curr.ponto;

        // If we have reached the destination cell,
        // we are done
        if (pt.x == (n-1) && pt.y == (n-1)) {
            resp = curr.dist;
            break;
        }

        // Otherwise dequeue the front cell in the queue
        // and enqueue its adjacent cells
        fila_visita.pop();


        point left={pt.x+1, pt.y};
        point down={pt.x,pt.y+1};
        // if adjacent cell is valid, has path and
        // not visited yet, enqueue it.
        if (isValid(n,left.x, left.y) && matrix[left.x][left.y] &&
            !visited[left.x][left.y])
        {
            // mark cell as visited and enqueue it
            visited[left.x][left.y] = true;
            queuenode Adjcell = { left, curr.dist + 1 };
            fila_visita.push(Adjcell);
        }

        // if adjacent cell is valid, has path and
        // not visited yet, enqueue it.
        if (isValid(n,down.x, down.y) && matrix[down.x][down.y] &&
            !visited[down.x][down.y])
        {
            // mark cell as visited and enqueue it
            visited[down.x][down.y] = true;
            queuenode Adjcell = { down, curr.dist + 1 };
            fila_visita.push(Adjcell);
        }
    }


    cout << resp << endl;




    return 0;
}
	  	 	 				 	  	 		 		  			