Background

Translated from NordicOI 2023 Problem C Island Alliances.

Problem Description

There are $n$ islands on the sea. Among them, there are $m$ pairs of islands that have a hostile relationship. However, because the weather is harsh, an island cannot survive alone, so some islands propose forming “alliances”.

There are $q$ alliance requests. Each request contains a pair $(a_i,b_i)$, meaning that island $a_i$ wants to form an alliance with island $b_i$. However, due to hostile relationships, this proposal may not be accepted. If none of the islands in the alliance that originally contains $a_i$ has a hostile relationship with any of the islands in the alliance that contains $b_i$, then the two sides can agree to form an alliance; otherwise, they will refuse.

Note that once the alliance is approved, the two alliances are immediately merged into a single alliance.

Input Format

The first line contains three integers $n$, $m$, and $q$, meaning there are $n$ islands, $m$ hostile pairs of islands, and $q$ proposals.

The next $m$ lines each contain a pair of integers $(u_i,v_i)$, meaning island $u_i$ and island $v_i$ are hostile to each other.

Then the next $q$ lines each contain two integers $a_i$ and $b_i\ (a_i \neq b_i)$, meaning island $a_i$ wants to form an alliance with island $b_i$.

Output Format

For each proposal, output APPROVE if it is accepted; otherwise output REFUSE.

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

Hint

This problem uses bundled testdata.

• 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): It is guaranteed that the number of refused proposals is at most once.
• Subtask 5 (25 points): No special constraints.

For all testdata, $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 distinct.

Translated by ChatGPT 5