#E. 【基础】舞伴

    Type: Default 1000ms 128MiB

【基础】舞伴

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

小明在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

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45