Problem Description

There are $n$ islands in the sea, with $m$ pairs of islands having hostile relationships. Due to harsh weather conditions, islands cannot survive alone, so some islands propose forming "alliances."

There are $q$ alliance requests, each containing a pair $(a_i, b_i)$, indicating that island $a_i$ wants to form an alliance with island $b_i$. However, considering the hostile relationships between some islands, this proposal may not be approved. The alliance will be approved if none of the islands in $a_i$'s current alliance have hostile relationships with any of the islands in $b_i$'s current alliance. Otherwise, the alliance will be refused.

Note that once an alliance is approved, the two alliances immediately merge into one.

Input Format

The first line contains three integers $n$, $m$, and $q$, representing the number of islands, the number of hostile relationships, and the number of alliance requests, respectively.

The next $m$ lines each contain a pair of integers $(u_i, v_i)$, indicating that island $u_i$ and island $v_i$ have a hostile relationship.

The following $q$ lines each contain two integers $a_i$ and $b_i$ ($a_i \neq b_i$), representing that island $a_i$ wants to form an alliance with island $b_i$.

Output Format

For each request, output APPROVE if the alliance is approved, otherwise output REFUSE.

Sample Input and Output

Sample Input #1

3 1 2
1 2
2 1
1 3

Sample Output #1

REFUSE
APPROVE

Sample Input #2

8 3 7
1 2
2 3
3 4
1 2
4 5
5 6
7 8
3 4
1 3
2 4

Sample Output #2

REFUSE
APPROVE
APPROVE
APPROVE
REFUSE
APPROVE
APPROVE

Notes

This problem uses batched testing.

• Subtask 1 (15 points): $2 \leq n \leq 500$, $1 \leq m \leq 10^5$, $1 \leq q \leq 10^5$.
• Subtask 2 (17 points): $2 \leq n \leq 10^5$, $1 \leq m \leq 250$, $1 \leq q \leq 10^5$.
• Subtask 3 (20 points): $2 \leq n \leq 5000$, $1 \leq m \leq 5000$, $1 \leq q \leq 10^5$.
• Subtask 4 (23 points): There is at most one instance where the alliance request is refused.
• Subtask 5 (25 points): No additional constraints.

For all test cases, $2 \le n \le 10^5$, $1 \le m, q \le 10^5$, $1 \le a_i, b_i \le n$, and each pair $(a_i, b_i)$ is unique.

见题面 Input 部分

见题面 Output 部分