岛屿王国由 $$$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
注意
最后一个示例测试用例的冲突图如下所示。每个圆圈代表一个岛屿。