题目描述

一般三分图的匹配需要运用基于拉格朗日松弛的分支定界法，并运用启发式算法得到较优的初始下界。已被证明是 NPC 问题。出题者在此说明一般三分图的匹配可以解决本题。
三个点集 $X, Y, Z$ ，同一点集之间没有边，$X,Z$ 点集之间没有边，$X,Y$ 点集之间有边，$Y,Z$ 点集之间有边。
求三分图的最大匹配。

注意：本题的一个匹配指的是 $X$ 点集中的点 $i$ ， $Y$ 点集中的点 $j$ , $Z$ 点集中的点 $k$ 被两条边相连。三分图最大匹配指的是满足上述条件的不相交点集 $\{ i , j , k \}$ 的个数

输入格式

第 1 行五个整数 $n_1,n_2,n_3,m_1,m_2$
分别表示 $X,Y,Z$ 点集的点数， $X,Y$ 之间的边数，$Y,Z$ 之间的边数。
然后 $m_1$ 行，一行两个整数 $a,b$ ，表示 $x_a$ 和 $y_b$ 之间有边。
然后 $m_2$ 行，一行两个整数 $a,b$ ，表示 $y_a$ 和 $z_b$ 之间有边。

输出格式

一行一个整数，三分图的最大匹配数。

3 4 5 6 6
1 1
1 3
2 2
2 4
3 1
3 3
1 2
2 1
2 3
3 2
4 4
4 5

2

3 3 3 5 4
1 2
2 3
2 2
1 3
3 1
1 2
3 3
3 2
2 1

3

数据范围与提示

输入可能存在重边。
对于 $100\%$ 的数据， $n_1,n_2,n_3 \leq 1000,m_1,m_2 \leq 5000$。