islandalliances — NOINordic contest
Task type: batch | Time limit: 5 s | Memory limit: 1024 MB | Difficulty: 17
Algorithms: hash map, union-find, data structures, tree map, small to large

\problemname{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!

\section*{Input}
The input consists of:
\begin{itemize}
  \item 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.
  \item $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.
  \item $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.
\end{itemize}

\section*{Output}
Output $q$ lines, where the $i$th line should be ``\texttt{REFUSE}'' if the $i$th
proposal should be refused, or ``\texttt{APPROVE}'' if the $i$th proposal should
be approved.

\section*{Scoring}
\begin{tabular}{|l|l|l|}
    \hline
    Group & Points & Constraints \\ \hline
    1     &  15  & $2 \leq N \leq 500$,    $1 \leq M \leq 10^5$,   $1 \leq Q \leq 10^5$ \\ \hline % adjacency matrix O(n^3)
    2     &  17  & $2 \leq N \leq 10^5$,   $1 \leq M \leq 250$,    $1 \leq Q \leq 10^5$ \\ \hline % union find with global edge list O(mq)
    3     &  20  & $2 \leq N \leq 5\,000$, $1 \leq M \leq 5\,000$, $1 \leq Q \leq 10^5$ \\ \hline % union find tracking edge sets O(nm)
    4     &  23  & $2 \leq N \leq 10^5$,   $1 \leq M \leq 10^5$,   $1 \leq Q \leq 10^5$, maximum of one ``\texttt{REFUSE}`` \\ \hline   % binary search
    5     &  25  & $2 \leq N \leq 10^5$,   $1 \leq M \leq 10^5$,   $1 \leq Q \leq 10^5$ \\ \hline %  O(m log n + (n+q) \alpha(n))
\end{tabular}



Starter code: