Recursive circuit

In the layout of a recursive microcircuit, there are $N$ contacts in total, and some pairs of contacts are connected directly by conductive paths. The circuit also has $S$ sub-circuits, each an exact copy of this circuit.

The layout has three types of contacts:

1. Input contacts of the circuit ($K$ contacts). These are the only contacts that connect the circuit to external conductive paths.
2. Input contacts of the nested sub-circuits ($S \cdot K$ contacts).
3. Auxiliary contacts.

All these contacts can be connected with each other by conductive paths without any restrictions.

Signals travel along conductive paths. When a signal reaches a contact, it can follow any path connected to that contact. If an external signal reaches an input contact of a sub-circuit, it can enter the sub-circuit and travel further along its paths. If an internal signal reaches an input contact of a sub-circuit, it can leave the sub-circuit and travel outside the circuit (if there are paths outside, and if the external circuit is itself a sub-circuit of another circuit).

Consider the outermost circuit, with nothing outside it. Determine whether two specified input contacts of the circuit are connected by paths. Two contacts are connected if a signal can reach one from the other, possibly entering various sub-circuits a finite number of times.

Besides connectivity, find how deep the signal must go into the sub-circuits to reach one contact from the other. The outermost circuit has nesting depth 0. Its sub-circuits have depth 1, their sub-circuits have depth 2, and so on. For any signal path, the critical depth is the maximum nesting level among all circuits whose conductive paths the signal travels. Find the minimal critical depth over the paths between two given input contacts of the outermost circuit.

The first line contains four integers: $N$ (the number of contacts in the layout), $K$ (the number of input contacts of the circuit), $S$ (the number of sub-circuits), and $M$ (the number of conductive paths) ($1 \le K \le 100000$, $0 \le S \le 1000$, $K (S + 1) \le N \le 100000$, $0 \le M \le 100000$).

Each of the following $M$ lines defines a conductive path by two integers $a$ and $b$, the numbers of the contacts it connects directly ($1 \le a \neq b \le N$).

Contacts are numbered from $1$ to $N$. Input contacts of the circuit are numbered from $1$ to $K$. Input contacts of the $t$-th sub-circuit are numbered from $tK + 1$ to $tK + K$ (for $1 \le t \le S$). The $j$-th input contact of the $t$-th sub-circuit is the $(tK + j)$-th contact of the external circuit layout. The remaining contacts, if any, are auxiliary.

The next line contains $Q$, the number of queries ($1 \le Q \le 100000$). Each of the following $Q$ lines contains two integers $u$ and $v$, the numbers of two input contacts of the outermost circuit ($1 \le u \neq v \le K$).

Print $Q$ integers, one per line. The $r$-th number is the nesting depth needed to get from one of the two input contacts of the $r$-th query to the other. If the other input contact cannot be reached, print $-1$ instead.