[Solution] Kingdom of Islands solution codeforces | ICPC WF Moscow Invitational Contest

Kingdom of Islands solution codeforces

The Kingdom of Islands consists of pp 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 nn 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 kk 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.

Kingdom of Islands solution codeforces

Input

The first line of the input consists of two integers pp and nn (1pn1051≤p≤n≤1051p1041≤p≤104).

The second line consists of nn integers s1,s2,,sns1,s2,…,sn (1sip1≤si≤p). The integer sisi denotes that the ii-th jarl rules over the island number sisi. It is guaranteed that each island is ruled by at least one jarl.

The third line consists of a single integer kk (0k200≤k≤20).

Then kk lines follow. The jj-th of these lines consists of two distinct integers ajaj and bjbj (1aj<bjn1≤aj<bj≤n), denoting that the relation between the ajaj-th jarl and the bjbj-th jarl differs from traditional. It is guaranteed that no pair of jarls appears twice in this list.

Kingdom of Islands solution codeforces

Output

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

Examples
input

Copy
4 4
1 2 3 4
1
2 3
output

Copy
3
1 4 2

Kingdom of Islands solution codeforces

input

Copy
2 4
1 1 2 2
1
3 4
output

Copy
3
2 4 3
input

Copy
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
output

Copy
6
8 6 5 4 2 1

Kingdom of Islands solution codeforces

Note

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


 

Kingdom of Islands solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment