#P15514. [Nordic2023]Island Alliances

    ID: 14729 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900并查集数据结构图论算法基础模拟

[Nordic2023]Island Alliances

题目描述

在广阔的海洋中有 nn 个岛屿,编号为 11 到 nn。每个岛屿一开始都是一个独立主权国家。

不过,国家数量太多使外交事务变得十分复杂,因此岛民们决定把一些国家合并成更大但数量更少的国家。

然而,有 mm 对岛屿的居民彼此不信任,拒绝成为同一个国家的一部分。

现在岛民们给出了 qq 个合并提案,你需要按顺序处理。第 ii 个提案要求将包含岛屿 aia_i 的国家与包含岛屿 bib_i 的国家合并。

如果两个国家中存在一对互不信任的岛屿,那么该提案必须被拒绝;否则提案被批准,这两个国家中的所有岛屿从此属于同一个国家。

请你判断每个提案应当被拒绝还是批准。

输入格式

第一行输入三个整数 n,m,qn,m,q,分别表示岛屿数、互不信任的岛屿对数、提案数。

接下来 mm 行,每行输入两个整数 ui,viu_i,v_i,表示岛屿 uiu_i 和 viv_i 的居民互不信任。

保证每一对 (ui,vi)(u_i,v_i) 最多出现一次。

接下来 qq 行,每行输入两个整数 ai,bia_i,b_i,描述第 ii 个合并提案。

保证每个提案在提出时都不会要求一个国家与自己合并,也就是说,在处理第 ii 个提案时,aia_i 与 bib_i 一定属于不同的当前国家。

输出格式

输出 qq 行。

对于第 ii 个提案:

  • 如果应该拒绝,输出 REFUSE;
  • 如果应该批准,输出 APPROVE。

样例 1

输入

3 1 2
1 2
2 1
1 3

输出

REFUSE
APPROVE

样例 2

输入

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

数据范围与计分

子任务 分值 限制
1 15 2≤N≤5002\le N\le 500,1≤M≤1051\le M\le 10^5,1≤Q≤1051\le Q\le 10^5
2 17 2≤N≤1052\le N\le 10^5,1≤M≤2501\le M\le 250,1≤Q≤1051\le Q\le 10^5
3 20 2≤N≤50002\le N\le 5000,1≤M≤50001\le M\le 5000,1≤Q≤1051\le Q\le 10^5
4 23 2≤N≤1052\le N\le 10^5,1≤M≤1051\le M\le 10^5,1≤Q≤1051\le Q\le 10^5,最多只有一次 REFUSE
5 25 2≤N≤1052\le N\le 10^5,1≤M≤1051\le M\le 10^5,1≤Q≤1051\le Q\le 10^5