1932: 【基础】舞伴

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:24 解决:8

题目描述

小明在A公司工作,小红在B公司工作。这两个公司的员工有一个特点:一个公司的员工都是同性。A公司有N名员工,其中有P对朋友关系。B公司有M名员工,其中有Q对朋友关系。

朋友的朋友一定还是朋友。每对朋友关系用两个整数(Xi,Yi)组成,表示朋友的编号分别为Xi,Yi。男人的编号是正数,女人的编号是负数。小明的编号是1,小红的编号是-1。

大家都知道,小明和小红是朋友。现举办一场舞会,每个人要找一个异性作为自己的舞伴,那么,请你写一个程序求出两公司之间,通过小明和小红认识的人最多一共能组成多少对舞伴。(包括他们自己)

输入

第1行,4个空格隔开的正整数N,M,P,Q。
之后P行,每行两个正整数Xi,Yi。
之后Q行,每行两个负整数Xi,Yi。
N,M<=10000,P,Q<=20000。

输出

一行,一个正整数,表示通过小明和小红认识的人最多一共能组成多少对舞伴。(包括他们自己)

样例输入 复制

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

样例输出 复制

2