Volcanoes

1000ms

262144K

Description:

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).

Input:

The first line contains two integers n (1 ≤ n ≤ 10⁹) and m (1 ≤ m ≤ 10⁵). 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.

Output:

Print one integer, the minimum time in which Iahub can arrive at cell (n, n). If no solution exists (there is no path to the final cell), print -1.

Sample Input:

4 2
1 3
1 4

Sample Output:

Sample Input:

Sample Output:

Sample Input:

2 2
1 2
2 1

Sample Output:

-1

Note:

Consider the first sample. A possible road is: (1, 1) → (1, 2) → (2, 2) → (2, 3) → (3, 3) → (3, 4) → (4, 4).

Informação

Provedor Codeforces

Código CF383B