题目描述

Katniss is in a very long straight tunnel and wants to get out of it. She can move along the tunnel in both directions. There is exactly one hatch in the tunnel, and if she reaches it, she can exit.

Unfortunately, it's not that simple. There are grates blocking the entire width of the tunnel at $n$ locations. The grates are locked, and Katniss cannot pass through a grate until she unlocks it. Fortunately, there are $n$ keys located at $n$ points along the tunnel. Each grate can be unlocked by exactly one of these $n$ keys. Once a grate is unlocked, Katniss can freely and repeatedly pass through it. She can pick up and hold an unlimited number of keys.

Katniss knows her own location, as well as the locations of all $n$ keys, all $n$ grates, and the hatch. She also knows which key unlocks which grate. Determine the minimum distance she must travel to escape.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5 \cdot 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $s$, and $h$, denoting the number of grates, the~initial coordinate of Katniss, and the coordinate of the hatch ($1 \le n \le 2 \cdot 10^5$; $-10^6 \le s, h \le 10^6$).

The $i$-th of the following $n$ lines contains two integers $k_i$ and $g_i$, denoting the coordinate of the $i$-th key and the coordinate of the grate that can be unlocked with this key ($-10^6 \le k_i, g_i \le 10^6$).

All $2n+2$ integers $s$, $h$, $k_i$, and $\ell_i$ are distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输出格式

For each test case, print the minimum possible length of Katniss' escape route. If it is impossible to escape, print $-1$ instead.

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

提示

In the first test case, one of the shortest escape routes goes as follows: $5$ (initial) $\rightarrow$ $3$ (pick up key $1$) $\rightarrow$ $7$ (unlock grate $1$) $\rightarrow$ $9$ (pick up key $4$) $\rightarrow$ $1$ (unlock grate $4$) $\rightarrow$ $-1$ (pick up key $3$) $\rightarrow$ $2$ (pick up key $5$) $\rightarrow$ $10$ (unlock grate $5$) $\rightarrow$ $11$ (unlock grate $3$) $\rightarrow$ $13$ (hatch).