#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/5/problems/F

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/5/problems/F

Repovive

Shortest Path on Intervals - Repovive Standard Round 2 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

5F. Shortest Path on Intervals

3000 ptstype :zen to enter zen mode

by Repovive Team

Time: 3sMemory: 512 MB

You are given $n$ intervals. The $i$ -th interval is represented by $[l_i, r_i]$ .

We construct an undirected graph with $n$ vertices, where each vertex represents one of the intervals. There is an edge between vertex $i$ and vertex $j$ ( $i \neq j$ ) if and only if their corresponding intervals intersect (i.e., $\max(l_i, l_j) \le \min(r_i, r_j)$ ). The weight of this edge is defined as $\min(i, j)$ .

Your task is to find the length of the shortest path from vertex $1$ to vertex $n$ in this graph. If there is no path between them, output $-1$ .

Constraints

$1 \le t \le 100$
$2 \le n \le 10^5$
$1 \le l_i \le r_i \le 2n$
The sum of $n$ over all test cases does not exceed $10^5$ .

Input

t

\left. \begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

Explanation

Case 1

There is no intersection between the first interval and any other interval, so it is impossible to reach the destination.

Case 2

The optimal path is to move from the first interval to the second interval (with a cost of $\min(1, 2) = 1$ ), and then from the second interval to the fourth interval (with a cost of $\min(2, 4) = 2$ ). The total cost is $1 + 2 = 3$ .

Case 3

To reach the fifth interval, the path must go through all intervals sequentially. The path goes from the first interval to the second, then the third, fourth, and finally the fifth. The costs of traversing these edges are $1$ , $2$ , $3$ , and $4$ , respectively, resulting in a total cost of $10$ .

Output

Case 1

-1

Case 2

Case 3

You are given $n$ intervals. The $i$ -th interval is represented by $[l_i, r_i]$ .

Your task is to find the length of the shortest path from vertex $1$ to vertex $n$ in this graph. If there is no path between them, output $-1$ .

Constraints

$1 \le t \le 100$
$2 \le n \le 10^5$
$1 \le l_i \le r_i \le 2n$
The sum of $n$ over all test cases does not exceed $10^5$ .

t

\left. \begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t