P10648 [NordicOI 2023] Island Alliances

Translated from [NordicOI 2023 Problem C](https://noi23.kattis.com/contests/noi23/problems/islandalliances) Island Alliances.

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.

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

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

**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