28363번 - 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!

입력

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 $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.

제한

서브태스크

힌트