Description

The employees of each company share one characteristic: everyone in the same company is of the same sex.

Company A has $N$ employees with $P$ friend pairs. Company B has $M$ employees with $Q$ friend pairs. Friends of friends are also friends.

Each friend pair is given as two integers $(X_i, Y_i)$, indicating the IDs of the two friends are $X_i$ and $Y_i$. Male IDs are positive numbers, and female IDs are negative numbers. Xiao Ming’s ID is $1$, and Xiao Hong’s ID is $-1$.

It is known that Xiao Ming and Xiao Hong are friends. Please write a program to find the maximum total number of couples that can be formed between the two companies via people known through Xiao Ming and Xiao Hong (including themselves).

Input Format

The first line contains $4$ space-separated positive integers $N,M,P,Q$.

Then follow $P$ lines, each containing two positive integers $X_i, Y_i$.

Then follow $Q$ lines, each containing two negative integers $X_i, Y_i$.

Output Format

Output a single positive integer on one line, representing the maximum total number of couples that can be formed via people known through Xiao Ming and Xiao Hong (including themselves).

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

2

Hint

For $30 \%$ of the testdata, $N,M \le 100$, $P,Q \le 200$.

For $80 \%$ of the testdata, $N,M \le 4 \times 10^3$, $P,Q \le 10^4$.

For $100 \%$ of the testdata, $N,M \le 10^4$, $P,Q \le 2 \times 10^4$.

Translated by ChatGPT 5