Problem Description

You are given a simple directed graph $ G $ with $ N $ vertices and $ A+B $ edges. The vertices are numbered $1, 2, \ldots, N$.

In this graph, $ A $ edges are colored red and the remaining $ B $ edges are colored blue.

Let $ G' $ be the graph obtained by removing all blue edges from $ G $.

Find the maximum number of edges in a graph $ G'' $ that satisfies the following conditions:

• $ G'' $ is obtained from $ G $ by removing any number (including zero) of blue edges.
• The maximum flow value from vertex $ 1 $ to vertex $ N $ in $ G' $ and $ G'' $ is the same, with all edge capacities set to $ 1 $.

Refer to this for information on maximum flow.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains integers $N(2 \leq N \leq 100)$, $A(1 \leq A \leq 200)$, and $B(1 \leq B \leq 200)$ separated by spaces.
• The next $ A+B $ lines contain the edge information of the graph. The $ i $-th line contains integers $X_i(1 \leq X_i \leq N)$ and $Y_i(1 \leq Y_i \leq N)$ separated by spaces, indicating the existence of edge $ (X_i, Y_i) $.
• $(X_1, Y_1), (X_2, Y_2), \ldots, (X_A, Y_A)$ are the red edges, and $(X_{A+1}, Y_{A+1}), (X_{A+2}, Y_{A+2}), \ldots, (X_{A+B}, Y_{A+B})$ are the blue edges.
• There is no $ i $ such that $ X_i = Y_i $. Also, for $i \neq j$, either $Y_i \neq Y_j$ or $X_i \neq X_j$ holds.

Output Format

Output the maximum number of edges in $ G'' $. The output should be to the standard output, followed by a newline.

Sample Input and Output

Sample Input #1

4 2 2
1 2
2 4
1 3
3 4

Sample Output #1

3

Sample Input #2

4 2 2
1 2
3 4
1 3
2 4

Sample Output #2

2

Sample Input #3

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

Sample Output #3

7

Sample Input #4

5 1 3
1 5
2 3
3 4
4 2

Sample Output #4

4

Sample Input #5

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

Sample Output #5

3

Notes/Hints

Sample Explanation 3

In this case, all blue edges can be added.

Sample Explanation 4

In this case, all blue edges can be added.

Sample Explanation 5

In this case, no blue edges can be added.

见题面 Input 部分

见题面 Output 部分