| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 3 | 3 | 3 | 100.000% |
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 2ドルn+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).