I. Incomplete Information Queries
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a directed graph with $$$n$$$ vertices and $$$\frac{n(n-1)}{2}$$$ edges. For each pair of different vertices $$$x$$$ and $$$y$$$, there is exactly one edge that is directed from $$$x$$$ to $$$y$$$ or from $$$y$$$ to $$$x$$$. You are not given the entire graph, but for each vertex $$$i$$$ you know $$$c_i$$$, the number of vertices reachable from it.

$$$m$$$ pairs of integers $$$(u_1, v_1), (u_2, v_2), \dots, (u_m, v_m)$$$ are given. You can apply zero or more operations to the graph. In each operation, you can choose a pair $$$(u_i, v_i)$$$ and make the edge between $$$u_i$$$ and $$$v_i$$$ bidirectional. For two vertices $$$a$$$ and $$$b$$$, define $$$f(a, b)$$$ as the minimum number of operations required to make vertex $$$b$$$ reachable from vertex $$$a$$$. If it is impossible to make $$$b$$$ reachable from $$$a$$$, then $$$f(a, b) = -1$$$.

There are $$$q$$$ independent queries about the graph. Each query is in one of the forms:

  1. S $$$a$$$ $$$b$$$ – You should find the smallest value of $$$f(a, b)$$$ over all possible graphs satisfying the given constraints.
  2. L $$$a$$$ $$$b$$$ – You should find the largest value of $$$f(a, b)$$$ over all possible graphs satisfying the given constraints.
Input

The first line of input contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m, q \le 5 \times 10^5$$$).

The next line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$).

Then $$$m$$$ lines follow. The $$$i^\text{th}$$$ of these lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$).

Then $$$q$$$ more lines follow. Each line contains a character $$$t$$$ followed by two integers $$$a$$$ and $$$b$$$ describing a query ($$$t \in \{ \texttt{S}, \texttt{L} \}$$$, $$$1 \le a, b \le n$$$).

You may assume that there exists at least one graph satisfying the constraints.

Output

For each query print an integer — the answer to the query.

Example
Input
5 3 3
4 3 5 1 2
5 1
1 2
2 4
S 1 3
L 1 2
S 4 1
Output
-1
0
2