图的着色

给定一个由 $ N $ 个顶点和 $ A+B $ 条边组成的简单有向图 $ G $。每个顶点都被标记为 $ 1,\ 2,\ …,\ N $。

这个图中有 $ A $ 条红色边和 $ B $ 条蓝色边。

我们将删除所有蓝色边得到的图称为 $ G' $。

请找出满足以下条件的图 $ G'' $ 中边数的最大值：

• $ G'' $ 是从 $ G $ 中删除 $ 0 $ 条或更多蓝色边后得到的图。
• 当将顶点 $ 1 $ 作为起点，顶点 $ N $ 作为终点时，$ G' $ 和 $ G'' $ 的最大流的值相等。其中所有边的容量均为 $ 1 $。

有关最大流的信息，请参阅这里。

输入以以下格式从标准输入中给出。

$ N $ $ A $ $ B $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ : $ X_{A+B} $ $ Y_{A+B} $

• 第一行包含三个整数，以空格分隔，分别为 $ N(2\ \leq\ N\ \leq\ 100) $、$ A(1\ \leq\ A\ \leq\ 200) $ 和 $ B(1\ \leq\ B\ \leq\ 200) $。
• 接下来的 $ A+B $ 行给出了图的边信息。其中第 $ i $ 行包含两个整数 $ X_i(1\ \leq\ X_i\ \leq\ N) $ 和 $ Y_i(1\ \leq\ Y_i\ \leq\ N) $，表示存在边 $ (X_i,\ Y_i) $。
• 边 $ (X_1,\ Y_1),\ (X_2,\ Y_2),\ …,\ (X_A,\ Y_A) $ 为红色边，边 $ (X_{A+1},\ Y_{A+1}),\ (X_{A+2},\ Y_{A+2}),\ ...,\ (X_{A+B},\ Y_{A+B}) $ 为蓝色边。
• 不存在 $ X_i\ =\ Y_i $ 的 $ i $。并且，如果 $ i\ \neq\ j $，则 $ Y_i\ \neq\ Y_j $ 或 $ X_i\ \neq\ X_j $。

输出 $ G'' $ 的边数的最大值。将结果输出到标准输出，并在末尾包含换行符。

样例 #1

样例输入 #1

4 2 2
1 2
2 4
1 3
3 4

样例输出 #1

3

样例 #2

样例输入 #2

4 2 2
1 2
3 4
1 3
2 4

样例输出 #2

2

样例 #3

样例输入 #3

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

样例输出 #3

7

样例 #4

样例输入 #4

5 1 3
1 5
2 3
3 4
4 2

样例输出 #4

4

样例 #5

样例输入 #5

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

样例输出 #5

3

样例解释 3

在这种情况下，可以添加所有蓝色边。

样例解释 4

在这种情况下，也可以添加所有蓝色边。

样例解释 5

在这种情况下，无法添加任何蓝色边。