Maximum Couples via Friend Introductions

There are two companies with a unique characteristic: all employees in each company are of the same gender. Company A employs N people (all males) and Company B employs M people (all females). Each company has its own friendship network. In Company A there are P friendship pairs and in Company B there are Q friendship pairs. Friendship is transitive, meaning that "a friend of a friend is also a friend"; thus, the friendship relation partitions the employees into connected groups (cliques).

Every friendship pair is given as two integers \( (X_i, Y_i) \), representing the IDs of the two employees. In Company A the IDs are positive integers, and in Company B the IDs are negative integers. It is known that Xiao Ming (ID 1) works in Company A and Xiao Hong (ID -1) works in Company B, and they are friends. By virtue of this cross‐company friendship, every employee in Xiao Ming’s friendship group (i.e. the connected component containing 1 in Company A) can be introduced to every employee in Xiao Hong’s friendship group (i.e. the connected component containing -1 in Company B).

Your task is to determine the maximum number of couples (each pair consisting of one male and one female) that can be formed from the employees who can be mutually introduced through Xiao Ming and Xiao Hong. Note that one couple is a pairing of one person from Company A and one person from Company B. Clearly, the maximum number of couples available is the minimum between the size of Xiao Ming's connected group and the size of Xiao Hong's connected group, since each couple needs one member from each company. This count includes the couple formed by Xiao Ming and Xiao Hong themselves.

The friendship networks in each company are provided separately. For those employees who never appear in any friendship pair, assume they are isolated (i.e. they form a connected component of size one with themselves).

inputFormat

The first line contains four integers: N, P, M, and Q, where

• N: the number of employees in Company A (male, with positive IDs from 1 to N)
• P: the number of friendship pairs in Company A
• M: the number of employees in Company B (female, with negative IDs from -1 to -M)
• Q: the number of friendship pairs in Company B

Then follow P lines, each containing two integers \(X_i\) and \(Y_i\) representing a friendship pair in Company A.

Then follow Q lines, each containing two integers (both negative) representing a friendship pair in Company B.

outputFormat

Output a single integer which is the maximum number of couples that can be formed via introductions (by pairing one person from Company A’s connected component containing 1 and one person from Company B’s connected component containing -1).

The answer is the minimum of the sizes of the two connected components.

sample

3 2 3 1
1 2
2 3
-2 -3

1