Marriage Match

You may know the funny problem “The Stable Marriage Problem”. Now let’s find a new match algorithm.
Firstly the women and men stand in a line separately and each woman will choose the man she likes.
Then it’s your task to make a match for these people. You should choose m women and m men from the initial queues. Let them stand in a line separately by initial order. If the woman stands in the ith place do not like the man stands in the ith place, the match is unacceptable. To increase the possibility of the match, the women can accept the men their friends like. Please find out the maximal m.

There are several test cases.
Each test case starts with two integer p and q in a line means the number of women and the number of men.(0 < p , q <= 100000)
Then a line with p numbers follows means the queue of women. (The id ranges from 1 to p)
Then a line with q numbers follows means the queue of men. (The id ranges from 1 to q)
Then a line with p numbers which means the man the ith woman likes.
Then a line with an integer t, means the number of friendships between women.(0 < t < 100000)
Then t lines follow. Each line contains two numbers a and b means a and b are friends.(a!=b, 1 <= a, b <= p)
You may support the friendship can transmit. If a and b are friends and c and b are friends, then a and c are friends. Notice every woman will have no more than five friends.

For each case, output the maximal m in one line.

4 4
1 3 2 4
1 4 2 3
2 3 1 2
2
1 2
3 4

2

HDU 2009-11 Programming Contest