← 返回题目列表

Codeforces · 1578/K

K. 岛屿王国

中文机器翻译题面 查看原题

岛屿王国由 $$$p$$$ 岛屿组成。作为国王,您统治整个王国,而每个岛屿则由您统治下的一个或多个领主统治。您管辖下的领主总数为 $$$n$$$。

王国的每个岛屿都有自己强大的传统,因此统治同一岛屿的领主们相互支持,从不发生冲突。这种优势的缺点是居住在不同岛屿上的人们之间存在文化冲突。因此,统治不同岛屿的两个领主发生了冲突。

然而,近年来,领主之间的传统关系发生了一些变化。据您所知,总共有$$$k$$$对领主,其中两个领主之间的关系与传统不同。也就是说,如果您认识的两个领主统治同一个岛屿,那么这些领主就会发生冲突。如果他们统治不同的岛屿,那么他们就克服了文化分歧,他们之间就不再有冲突了。

作为一个真正负责任的国王,你担心王国是否即将发生重大冲突。为了估计当前的情况,您希望找到尽可能最大的领主群体,使得该群体中每两个领主都会发生冲突。

输入

输入的第一行包含两个整数 $$$p$$$ 和 $$$n$$$ ($$$1 \le p \le n \le 10^5$$$; $$$1 \le p \le 10^4$$$)。

第二行由 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le p$$$) 组成。整数 $$$s_i$$$ 表示第 $$$i$$$ 号领主统治着编号为 $$$s_i$$$ 的岛屿。确保每个岛屿至少由一名领主统治。

第三行由一个整数 $$$k$$$ ($$$0 \le k \le 20$$$) 组成。

然后是 $$$k$$$ 行。这些行中的第 $$$j$$$ 由两个不同的整数 $$$a_j$$$ 和 $$$b_j$$$ ($$$1 \le a_j < b_j \le n$$$) 组成,表示第 $$$a_j$$$-th jarl 和第 $$$b_j$$$-th jarl 之间的关系与传统的不同。保证没有一对领主在此列表中出现两次。

输出

在第一行中打印 $$$1$$$ 和 $$$n$$$ 之间的单个整数 $$$q$$$ — 成对冲突组中 jarls 的最大可能数量。在第二行中,打印 $$$q$$$ 之间的不同整数 $$$1$$$ 和 $$$n$$$ - 组中 jarls 的数量。领主的数量可以按任何顺序打印。

示例

输入 #1

4 4
1 2 3 4
1
2 3

输出 #1

3
1 4 2

输入 #2

2 4
1 1 2 2
1
3 4

输出 #2

3
2 4 3

输入 #3

4 8
1 1 1 2 2 3 4 4
7
1 2
2 3
3 6
4 5
5 7
2 7
3 8

输出 #3

6
8 6 5 4 2 1

注意

最后一个示例测试用例的冲突图如下所示。每个圆圈代表一个岛屿。