P14610 [NWRRC 2025] Keys and Grates

Katniss 身处一条非常长的笔直隧道中，想要离开。她可以沿着隧道双向移动。隧道中恰好有一个舱口，如果她到达那里，就可以离开。 不幸的是，事情没那么简单。隧道中有 $n$ 个位置设有栅栏，阻挡了整个隧道的宽度。栅栏被锁住了，Katniss 在解锁之前无法通过栅栏。幸运的是，隧道中有 $n$ 个钥匙分布在 $n$ 个点上。每个栅栏恰好可以用这 $n$ 把钥匙中的一把来解锁。一旦栅栏被解锁，Katniss 就可以自由且反复地通过它。她可以拾取并持有无限数量的钥匙。 Katniss 知道她自己的位置，以及所有 $n$ 把钥匙、所有 $n$ 个栅栏和舱口的位置。她还知道哪把钥匙可以解锁哪个栅栏。请确定她逃脱必须行走的最小距离。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 5 \cdot 10^4$）。接下来是测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$s$ 和 $h$，分别表示栅栏的数量、Katniss 的初始坐标和舱口的坐标（$1 \le n \le 2 \cdot 10^5$；$-10^6 \le s, h \le 10^6$）。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $k_i$ 和 $g_i$，分别表示第 $i$ 把钥匙的坐标和可以用这把钥匙解锁的栅栏的坐标（$-10^6 \le k_i, g_i \le 10^6$）。 所有 $2n+2$ 个整数 $s$、$h$、$k_i$ 和 $g_i$ 都是互不相同的。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 Katniss 逃脱路线的最小可能长度。如果无法逃脱，则输出 $-1$。

在第一个测试用例中，其中一条最短逃脱路线如下：$5$（初始）$\rightarrow$ $3$（拾取钥匙 $1$）$\rightarrow$ $7$（解锁栅栏 $1$）$\rightarrow$ $9$（拾取钥匙 $4$）$\rightarrow$ $1$（解锁栅栏 $4$）$\rightarrow$ $-1$（拾取钥匙 $3$）$\rightarrow$ $2$（拾取钥匙 $5$）$\rightarrow$ $10$（解锁栅栏 $5$）$\rightarrow$ $11$（解锁栅栏 $3$）$\rightarrow$ $13$（舱口）。 --- 翻译由 DeepSeek V3 完成