Modern Announce Network

Teenagers today keep in touch on social networks.

In one high school, $N$ students use a social network called ICPC (International Community for Programming Contest). Some pairs among those $N$ students are friends on the network and can send messages to each other. Of the $N$ students, $A$ first grade students, $B$ second grade students and $C$ third grade students belong to the Programming Society. Some students belong to no society, so $A+B+C$ can be smaller than $N$.

Members of the same grade get along, so each grade has one group chat. The moment one member of a grade receives a message, every member of that grade receives it as well. Different grades do not get along, and there is no group chat for the whole society or for the whole school.

The administrator of the society has no account on the network. To announce a message, the administrator tells it in person to one of the $N$ students, and that student spreads it on the network over the group chats and the friend links. Once at least one member of every grade has the message, the announcement counts as delivered to the whole society.

Contacting a friend is a bother, so the society wants as few of those contacts as possible. One contact between friends is one message passed between two students who are friends. Messages that spread inside a grade group chat do not count. Find the smallest number of contacts between friends needed to announce a message to every society member, and the id of the student the administrator should tell first to reach that number.

The input holds a single test case in this format.

N A B C
a1 ... aA
b1 ... bB
c1 ... cC
M
x1 y1
...
xM yM

The first line has four integers $N$, $A$, $B$ and $C$. $N$ is the number of students on the network, with $3 \le N \le 10000$. $A$, $B$ and $C$ are the numbers of first, second and third grade society members, with $1 \le A, B, C$ and $A+B+C \le N$. Each student is identified by an id between 1 and $N$, and no two students share an id.

The second line has the $A$ ids $a_1$ to $a_A$ of the first grade members. The third line has the $B$ ids $b_1$ to $b_B$ of the second grade members. The fourth line has the $C$ ids $c_1$ to $c_C$ of the third grade members. All of these ids are different.

The fifth line has one integer $M$, the number of friend pairs, with $2 \le M \le 500000$. Line $i$ of the next $M$ lines has two integers $x_i$ and $y_i$, which mean that the students with ids $x_i$ and $y_i$ are friends, with $1 \le x_i, y_i \le N$ and $x_i \ne y_i$. The same pair never appears twice, in either order.

Using friend links and grade group chats, a message can travel from any student to any other student.

Print the smallest number of contacts between friends needed to announce a message to every society member, then the id of the student the administrator tells the message to first, separated by one space. Messages inside a grade group chat do not count as contacts. When several students reach the smallest number, print the smallest such id.