Chain Combo in Dual-Hand Martial Arts

The legendary martial artist practices a special technique called "Left‐Right Mutual Combat", originally invented by Zhou Botong. In this technique, the movements of both hands in a vertical plane are recorded in a coordinate system with the origin at some fixed point. The x–axis points to the right, and the y–axis points upward. Any point in the plane is represented by its coordinates \((x,y)\).

There are n possible pause points, given by \(p_1=(x_1,y_1), p_2=(x_2,y_2), \dots, p_n=(x_n,y_n)\). The training process is divided into seconds. At the beginning of every second the left and right hands are each located at one of the pause points. At the end of each second, each hand may move (at most once per second) to another pause point if and only if there is an allowed move from its current point. (A hand may also choose not to move.)

The allowed moves are given by m conditions. Each condition is of the form: for either hand, when it is at pause point \(a\), it can move to pause point \(b\) and vice versa. All other movements are illegal.

However, there is a restriction when the hands are pausing: if the Manhattan distance between the two hands is less than \(d_{min}\) or greater than \(d_{max}\), then it will lead to disastrous consequences. That is, if the left hand is at point \(l\) and the right hand is at point \(r\), the distance must satisfy:

[ d_{min} \le |x_l - x_r| + |y_l - y_r| \le d_{max}. ]

There are also k special moves (or "finishing moves") available. The \(i^{th}\) special move can be executed when the left hand is at pause point \(v_i\) and the right hand is at pause point \(u_i\). A combo is defined as executing one special move and, after some seconds of legal movements, executing a different special move. Note that if two or more special moves share the same hand positions, they are considered distinct; hence if the initial state already qualifies for a different special move, the waiting time will be zero.

Your task is: for each \(1 \le i \le k\), given that the initial state is the one for the \(i^{th}\) special move \((v_i, u_i)\) (which is guaranteed to satisfy the Manhattan distance constraint), determine the minimum number of seconds of movement required so that the hands can be repositioned (via legal moves) to execute some special move \(j\) with \(j \ne i\). If it is impossible, output -1.

Input Format

The input consists of several parts:

• The first line contains three integers: \(n\) \(k\) \(m\).
• The next \(n\) lines each contain two integers \(x_i\) and \(y_i\) representing the coordinates of pause point \(p_i\) (\(1 \le i \le n\)).
• The following line contains two integers: \(d_{min}\) and \(d_{max}\).
• The next \(k\) lines each contain two integers: \(v_i\) and \(u_i\) (the required pause points for the \(i^{th}\) special move).
• The final \(m\) lines each contain two integers \(a\) and \(b\) indicating that a hand can legally move between pause points \(a\) and \(b\) (movement is bidirectional).

Output Format

Output a single line with \(k\) space‐separated integers. The \(i^{th}\) integer is the minimum number of seconds needed to chain (i.e. to move from the state corresponding to special move \(i\) to some state corresponding to special move \(j\), \(j \ne i\)). If it is impossible, output -1 for that \(i\).

inputFormat

The input begins with a line containing three integers: n k m.

Then follow n lines each with two integers x_i y_i for \(1 \le i \le n\).

The next line contains two integers: d_min d_max.

Then k lines follow. The \(i^{th}\) of these lines contains two integers: v_i u_i.

Finally, there are m lines; each line contains two integers a b, meaning a hand can move between pause points a and b (in both directions).

outputFormat

Output a single line containing k integers separated by spaces. The \(i^{th}\) integer is the minimum number of seconds required to reposition from the state of special move \(i\) to a state corresponding to a different special move. If it is impossible, output -1 for that \(i\).

sample

4 3 3
0 0
0 2
2 0
2 2
2 4
1 4
2 3
1 3
1 2
2 4
3 4

2 1 1