Kingdom of Islands

题意翻译

群岛王国由 $p$ 座岛屿组成。作为国王，你掌管整个王国，同时每座岛在你定下的规则下由一个或若干贵族管辖。总的来说，有 $n$ 个贵族处于你的管辖范围中。 王国中每座岛都有它各自的传统，所以掌管同一座岛的贵族们总是互相支持，并且不会发生冲突。这种互相支持的负面影响就是在不同岛屿定居的人们会产生文化冲突。因此，掌管两座不同的岛的两个贵族会起冲突。 然而，近几年贵族之间的传统关系之间起了一些变化。据你所知，有恰好 $k$ 对贵族之间的关系与传统以来的情况不同。也就是说，你知道的这些对贵族如果掌管同一座岛，那他们就会起冲突。如果他们掌管不同岛屿，他们就会超越文化分歧而不会产生任何冲突。 作为真正的负责国王，你对国家内部是否离一次大的争端很近十分担忧。为了估计目前的形势，你想要找到最大的一群贵族，使得这些贵族之间两两都有矛盾。 输入的第一行包含两个数 $p\ (1\le p\le 10^4)$ 和 $n\ (1\le p\le n\le 10^5)$。 第二行包含 $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$ 个贵族和第 $b_j$ 个贵族之间的关系不同于传统。保证没有任意一对贵族在这个列表中出现两次。 第一行输出一个整数 $q\ (1\le q\le n)$，表示最大的一群贵族中满足两两之间都有矛盾的贵族总数。第二行输出 $q$ 个两两不同的 $1$ 到 $n$ 范围之间的整数，表示这群贵族的编号。贵族的编号可以以任何顺序输出。 最后一组数据表示冲突的图如下。每个圆圈表示一座岛。 （图）

题目描述

The Kingdom of Islands consists of $ p $ islands. As the king, you rule over the whole kingdom, while each island is ruled over by one or several jarls under your rule. In total, there are $ n $ jarls under your jurisdiction. Each island of the kingdom has its own strong traditions, so jarls that rule over the same island support each other and never have conflicts. The downsides of such strength are cultural conflicts between people inhabiting different islands. Thus, two jarls that rule over different islands are in conflict. However, recent years brought a few changes to traditional relations between the jarls. To your knowledge, there are exactly $ k $ pairs of jarls such that relationships between two jarls in the pair are different from the traditional. That is, if two jarls of the pair you know rule over the same island, these jarls are in conflict. If they rule over different islands, then they overcome cultural disagreement and there is no conflict between them anymore. As a true responsible king, you are worried about whether the kingdom is close to a major conflict. In order to estimate the current situation, you would like to find the largest possible group of jarls such that every two jarls in the group are in conflict.

输入输出格式

输入格式

The first line of the input consists of two integers $ p $ and $ n $ ( $ 1 \le p \le n \le 10^5 $ ; $ 1 \le p \le 10^4 $ ). The second line consists of $ n $ integers $ s_1, s_2, \ldots, s_n $ ( $ 1 \le s_i \le p $ ). The integer $ s_i $ denotes that the $ i $ -th jarl rules over the island number $ s_i $ . It is guaranteed that each island is ruled by at least one jarl. The third line consists of a single integer $ k $ ( $ 0 \le k \le 20 $ ). Then $ k $ lines follow. The $ j $ -th of these lines consists of two distinct integers $ a_j $ and $ b_j $ ( $ 1 \le a_j < b_j \le n $ ), denoting that the relation between the $ a_j $ -th jarl and the $ b_j $ -th jarl differs from traditional. It is guaranteed that no pair of jarls appears twice in this list.

输出格式

In the first line print a single integer $ q $ between $ 1 $ and $ n $ — the largest possible number of jarls in a pairwise conflicting group. In the second line print $ q $ distinct integers between $ 1 $ and $ n $ — the numbers of jarls in the group. The numbers of jarls can be printed in any order.

输入输出样例

输入样例 #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

说明

The conflict graph for the last sample testcase is given below. Each circle represents an island.