题目描述

Bajtazar 身处一条非常长的一维隧道中，希望从唯一的出口回家。

隧道中有 $n$ 扇关闭的门，同时也有 $n$ 把钥匙。每把钥匙恰好能打开一扇门，并且每扇门都恰好有一把对应的钥匙。Bajtazar 在行走过程中可以拾取钥匙，并且可以携带任意多把钥匙。

Bajtazar 知道：

• 自己的初始位置 $s$；
• 出口位置 $h$；
• 每把钥匙的位置；
• 每扇门的位置；
• 每把钥匙对应哪扇门。

当 Bajtazar 第一次要穿过一扇关闭的门时，必须已经拿到对应的钥匙；拿到钥匙后即可打开该门并通过。

求 Bajtazar 到达出口所需行走的最短总距离。如果无论如何都无法离开隧道，输出 $-1$。

输入格式

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

$1\le t\le 5\cdot 10^4$。

对于每组数据：

第一行包含三个整数 $n,s,h$：

• $1\le n\le 2\cdot 10^5$；
• $-10^6\le s,h\le 10^6$。

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

• $k_i$：第 $i$ 把钥匙的位置；
• $g_i$：这把钥匙所能打开的门的位置；
• $-10^6\le k_i,g_i\le 10^6$。

每组数据中的 $2n+2$ 个坐标 $s,h,k_i,g_i$ 两两不同。

所有测试数据中 $n$ 的总和不超过 $2\cdot10^5$。

输出格式

对于每组数据输出一行：

• 若可以到达出口，输出所需的最短行走距离；
• 否则输出 -1。

样例

4
2 1 10
2 0
-1 5
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

15
32
-1
7

样例说明

第一组数据中，Bajtazar：

1. 从 $1$ 走到位置 $2$，拿到能打开位置 $0$ 处门的钥匙；
2. 穿过位置 $0$ 的门后走到 $-1$，拿到能打开位置 $5$ 处门的钥匙；
3. 再穿过位置 $5$ 的门走到出口 $10$。

第三组数据中，要穿过位置 $10$ 的门必须先取得位置 $90$ 的钥匙，但前往位置 $90$ 的途中又会被位置 $60$ 的门阻挡，而打开它所需的钥匙位于当前不可到达的位置 $70$，因此无法逃离。

子任务