1932 - 舞伴
题目描述
小明在A公司工作，小红在B公司工作。这两个公司的员工有一个特点：一个公司的员工都是同性。A公司有 N 名员工，编号为 1 \sim N ，其中有 P 对朋友关系。B公司有 M 名员工，编号为 -1 \sim -M，其中有 Q 对朋友关系。
朋友的朋友一定还是朋友。每对朋友关系用两个整数 (X_i,Y_i) 组成，表示朋友的编号分别为 X_i,Y_i。男人的编号是正数，女人的编号是负数。小明的编号是 1 ，小红的编号是 -1 。
大家都知道，小明和小红是朋友。现举办一场舞会，每个人要找一个异性作为自己的舞伴，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能组成多少对舞伴。（包括他们自己）
输入
第 1 行，4 个空格隔开的正整数 N,M,P,Q 。
之后 P 行，每行两个正整数 X_i,Y_i 。
之后 Q 行，每行两个负整数 X_i,Y_i 。
N,M \le 10000, P,Q \le 20000 。
输出
一行，一个正整数，表示通过小明和小红认识的人最多一共能组成多少对舞伴。（包括他们自己）
样例
输入
4 3 4 2 1 1 1 2 2 3 1 3 -1 -2 -3 -3
输出
2
来源
并查集
标签
