Shortest Path on Intervals - Repovive Standard Round 2 | Repovive

5F. Shortest Path on Intervals

3000 pts3s512 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

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

5F. Shortest Path on Intervals

Input

Output

Samples

5F. Shortest Path on Intervals

Constraints

Input

Output

Samples

Constraints