题目描述

题目译自 NordicOI 2023 T3 「Island Alliances」

在一片广阔的海洋中，有 $n$ 个岛屿，编号从 $1$ 到 $n$，每个岛屿都是一个主权国家。

然而，大量的国家使得外交事务变得非常复杂，所以岛民们决定通过加入更大的（但更少）国家来简化事情。这项努力事实证明比说起来容易，因为有 $m$ 对岛屿居民相互不信任，拒绝成为同一国家的一部分。

岛民们向你发送了 $q$ 个提案，你应该按顺序处理。第 $i$ 个提案要求包含岛屿 $a_i$ 的国家与包含岛屿 $b_i$ 的国家合并。如果两个国家包含一对居民相互不信任的岛屿，则应拒绝该提案，否则应批准该提案，并且两个国家中的所有岛屿将从此成为同一国家的一部分。

请帮助岛民们弄清楚哪些提案应该被拒绝，哪些应该被批准！

输入格式

输入第一行包含三个整数 $n, m, q$，分别表示岛屿的数量、不信任的岛屿对的数量和提案的数量。

接下来 $m$ 行，第 $i$ 行包含两个整数 $u_i, v_i$ $(1 \leq u_i, v_i \leq n, u_i\neq v_i)$，表示岛屿 $u_i$ 和 $v_i$ 的居民相互不信任。每对 $(u_i, v_i)$ 最多会被列出一次。

接下来 $q$ 行，其中第 $i$ 行包含两个整数 $a_i, b_i$ $(1 \leq a_i,b_i \leq n)$，描述第 $i$ 个提案。保证没有提案会要求一个国家与自己合并，这意味着在你收到第 $i$ 个提案时，$a_i$ 和 $b_i$ 一定属于不同的国家。

输出格式

输出 $q$ 行，其中第 $i$ 行应该是 REFUSE，如果第 $i$ 个提案应该被拒绝，或者 APPROVE，如果第 $i$ 个提案应该被批准。

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

数据范围与提示

详细子任务附加限制及分值如下表所示。