Acquapia

Acquapia is a small country crossed by several navigable rivers. Every river has its source in the mountains inside Acquapia and eventually flows into the sea; a river never flows into another river. Along its course (but not at its source) a river may split into two or more streams. There is a city at every point where a river begins, splits, or ends, and each city touches at most one river.

Rivers are the main means of transportation in Acquapia. Because the country is at war, ships cannot cross the sea and may travel only along rivers. To move between two cities a ship travels upstream (against the flow) up to some city, performs a stream change there, and then travels downstream (with the flow) to the destination. A stream change — switching from upstream to downstream navigation — is difficult and dangerous, so it should be avoided when possible; when it is unavoidable, it happens at exactly one city on the route. Travelling purely upstream or purely downstream needs no stream change.

Each river forms a tree rooted at its source with edges oriented downstream, so the route between any two connected cities is unique; hence the stream-change city, if any, is uniquely determined.

Given the rivers, the cities, and a list of queries, each a pair of cities $X$ and $Y$, answer for every query:

• Is it possible to navigate from city $X$ to city $Y$?
• If it is, does the ship need a stream change, and if so, at which city?

The input contains several test cases. The first line of each test case has four integers $C$, $R$, $S$ and $Q$ separated by single spaces: the number of cities ($2 \le C \le 10^3$), the number of rivers ($1 \le R \le C/2$), the number of river sections ($1 \le S \le C-1$) and the number of queries ($1 \le Q \le 2 \times 10^5$). Cities are numbered from $1$ to $C$.

The second line contains $R$ distinct integers, the cities that are river sources. Each of the next $S$ lines contains two integers $X$ and $Y$ ($X \ne Y$), meaning there is a river section flowing from city $X$ down to city $Y$. Each of the following $Q$ lines contains two integers $A$ and $B$ ($A \ne B$), a query.

The end of the input is the line $C = R = S = Q = 0$, which must not be processed.

For each test case, print $Q$ lines; the $i$-th line is the answer to the $i$-th query, in input order. Print a single empty line between the outputs of two consecutive test cases.

For a query $(A, B)$ print:

• $-1$ if it is impossible to navigate from $A$ to $B$;
• $0$ if navigation is possible without any stream change;
• otherwise, the number of the city where the stream change must be made.