Ski resort
本题没有可用的提交语言。
Description
Esomer loves skiing. However, he hates ski lifts because they are very long and always very cold. Determined not to suffer any longer, he has tried to come up with a route that minimizes the time spent on ski lifts. Unfortunately, he is not very good at interpreting the map of the pistes, so he has asked for your help.
The ski resort that Esomer visits can be represented as a directed acyclic graph with $n$ nodes and $m$ edges (the pistes). Additionally, there are $k$ ski lifts that connect node $a$ to node $b$. Interestingly, all ski lifts satisfy the condition that it is always possible to reach $a$ from $b$ without using any ski lift. It takes Esomer $1$ minute to traverse a piste or use a ski lift.
Esomer is interested in how much time he needs to spend on ski lifts in order to spend a total of $x$ minutes at the ski resort, without stopping at any node even for a second, while starting at node $y$. Esomer can finish his route at any node and leave for home as soon as he has spent the required $x$ minutes.
Please help Esomer.
The first line contains an integer $t$, the number of test cases. ($1 \le t \le 100$).
For each test case, the first line contains four integers $n$, $m$ and $k$. ($2 \le n \le 10^5$; $1 \le m \le \min(10^5, \frac{n \cdot (n-1)}{2})$; $1 \le k \le 10^2$).
Then, there are $m$ lines, each containing two integers, $u$ and $v$, indicating that there is an edge from $u$ to $v$. ($1 \le u, v \le n$).
It is guaranteed that the graph formed by the $m$ edges is acyclic.
Next, there are $k$ lines, each containing two integers, $a$ and $b$, indicating that there is a ski lift from $a$ to $b$. ($1 \le a, b \le n$; $a \neq b$).
It is guaranteed that it is possible to reach $a$ from $b$ without using any ski lift.
Finally, there is a line containing two integers $x$ and $y$, the number of minutes Esomer wants to spend at the ski resort, and the node at which he starts, respectively. ($1 \le x \le 10^9$; $1 \le y \le n$). It is guaranteed that Esomer can reach a ski lift from node $y$.
It is guaranteed that the sum of $n$ and $m$ over all test cases is at most $10^5$, while the sum of $k$ over all test cases is at most $10^2$.
For each test case, you should print an integer $s$, the minimum number of minutes Esomer needs to spend on ski lifts in order to spend a total of $x$ minutes at the ski resort.
Input
The first line contains an integer $t$, the number of test cases. ($1 \le t \le 100$).
For each test case, the first line contains four integers $n$, $m$ and $k$. ($2 \le n \le 10^5$; $1 \le m \le \min(10^5, \frac{n \cdot (n-1)}{2})$; $1 \le k \le 10^2$).
Then, there are $m$ lines, each containing two integers, $u$ and $v$, indicating that there is an edge from $u$ to $v$. ($1 \le u, v \le n$).
It is guaranteed that the graph formed by the $m$ edges is acyclic.
Next, there are $k$ lines, each containing two integers, $a$ and $b$, indicating that there is a ski lift from $a$ to $b$. ($1 \le a, b \le n$; $a \neq b$).
It is guaranteed that it is possible to reach $a$ from $b$ without using any ski lift.
Finally, there is a line containing two integers $x$ and $y$, the number of minutes Esomer wants to spend at the ski resort, and the node at which he starts, respectively. ($1 \le x \le 10^9$; $1 \le y \le n$). It is guaranteed that Esomer can reach a ski lift from node $y$.
It is guaranteed that the sum of $n$ and $m$ over all test cases is at most $10^5$, while the sum of $k$ over all test cases is at most $10^2$.
Output
For each test case, you should print an integer $s$, the minimum number of minutes Esomer needs to spend on ski lifts in order to spend a total of $x$ minutes at the ski resort.
1
6 5 2
2 4
5 4
6 2
6 4
3 4
2 6
4 6
4 2
1
10 13 5
3 4
9 4
5 8
9 2
4 2
1 10
10 9
9 8
7 5
5 2
9 3
10 2
3 2
8 10
2 9
4 3
4 1
5 7
12 7
1
2
Note
—
Problem idea: Esomer
Problem preparation: Esomer
Ocurrences: Advanced 10