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
来源

并查集

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题