K. 钥匙与栅栏（）

题目描述

Katniss 身处一条很长的笔直隧道中，想要逃出去。她可以沿隧道向左或向右移动。

隧道中有且仅有一个出口舱门。只要 Katniss 到达舱门所在位置，就能离开隧道。

然而，隧道中有 $n$ 道栅栏。每道栅栏都横跨整条隧道，并且处于锁定状态。在打开栅栏之前，Katniss 无法穿过它。

隧道中还放置着 $n$ 把钥匙，每把钥匙恰好能打开一道对应的栅栏，每道栅栏也恰好对应一把钥匙。

Katniss 到达一把钥匙的位置时可以捡起它，并且能够同时携带任意多把钥匙。打开某道栅栏后，她可以无限次自由穿过该栅栏。

Katniss 知道以下所有信息：

• 自己的初始位置；
• 出口舱门的位置；
• 所有钥匙的位置；
• 所有栅栏的位置；
• 每把钥匙能够打开哪一道栅栏。

请计算 Katniss 为逃离隧道至少需要移动多远。如果无论如何都无法到达出口，则输出 -1。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

每组测试数据的第一行包含三个整数 $n,s,h$，分别表示栅栏数量、Katniss 的初始坐标和出口舱门的坐标。

接下来 $n$ 行，第 $i$ 行包含两个整数 $k_i,g_i$：

• $k_i$ 表示第 $i$ 把钥匙的坐标；
• $g_i$ 表示这把钥匙能够打开的栅栏坐标。

所有 $2n+2$ 个坐标

$$s,h,k_1,g_1,k_2,g_2,\ldots,k_n,g_n$$

两两不同。

输出格式

对于每组测试数据，输出 Katniss 逃离隧道所需的最短路程。

如果无法逃离，输出 -1。

数据范围

$$1\le t\le 5\times 10^4,$$ $$1\le n\le 2\times 10^5,$$ $$-10^6\le s,h,k_i,g_i\le 10^6.$$

所有测试数据中：

$$\sum n\le 2\times 10^5.$$

样例

3
5 5 13
3 7
8 14
-1 11
9 1
2 10
4 40 0
20 80
50 30
70 60
90 10
1 -1 6
11 8

32
-1
7

样例说明

在第一组测试数据中，一条最短逃生路线如下：

$$5\rightarrow 3\rightarrow 7\rightarrow 9\rightarrow 1\rightarrow -1 \rightarrow 2\rightarrow 10\rightarrow 11\rightarrow 13.$$

沿途依次完成以下操作：

• 在坐标 $3$ 捡起钥匙 $1$；
• 在坐标 $7$ 打开栅栏 $1$；
• 在坐标 $9$ 捡起钥匙 $4$；
• 在坐标 $1$ 打开栅栏 $4$；
• 在坐标 $-1$ 捡起钥匙 $3$；
• 在坐标 $2$ 捡起钥匙 $5$；
• 在坐标 $10$ 打开栅栏 $5$；
• 在坐标 $11$ 打开栅栏 $3$；
• 最后到达坐标 $13$ 的出口。