Problem C
Island Alliances

In a vast ocean there are $n$ islands numbered from $1$ to $n$, where each island constitutes a sovereign state.

However, the large number of states is making foreign policy a very complicated matter, so the inhabitants of the islands have decided to simplify things by joining into larger (but fewer) states. This endeavour has turned out to be easier said than done, because there are $m$ pairs of islands whose inhabitants distrust each other and refuse to be part of the same state.

The islanders have sent you $q$ proposals that you should process in order. The $i$th proposal calls for the state containing island $a_ i$ to merge with the state containing island $b_ i$. If the two states contain a pair of islands whose inhabitants distrust each other the proposal should be rejected, but otherwise the proposal should be approved and all the islands in the two states will henceforth be part of the same state.

Please help the islanders figure out which proposals should be rejected and which should be approved!

Input

The input consists of:

• One line with three integers $n$, $m$, and $q$, the number of islands, the number of distrusting pairs of islands, and the number of proposals.

• $m$ lines, the $i$th of which contains two integers $u_ i$ and $v_ i$, where $1 \leq u_ i,v_ i \leq n$, $u_ i \neq v_ i$, meaning that the inhabitants of islands $u_ i$ and $v_ i$ distrust each other. Each pair $(u_ i, v_ i)$ will be listed at most once.

• $q$ lines, the $i$th of which contains two integers $a_ i$ and $b_ i$, where $1 \leq a_ i,b_ i \leq n$, describing the $i$th proposal. It is guaranteed that no proposal will ever call for a state to merge with itself, meaning that at the time when you receive the $i$th proposal, $a_ i$ and $b_ i$ are guaranteed to belong to different states.

Output

Output $q$ lines, where the $i$th line should be “REFUSE” if the $i$th proposal should be refused, or “APPROVE” if the $i$th proposal should be approved.

Scoring

3 1 2
1 2
2 1
1 3

REFUSE
APPROVE

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

REFUSE
APPROVE
APPROVE
APPROVE
REFUSE
APPROVE
APPROVE