P2078 Friends

Xiao Ming works at company A, and Xiao Hong works at company B.

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).

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 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).

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