Maximum Bike Trips

You are given two sets: a set of sources and a set of destinations. Each source is connected to one or more destinations by a bike path. A bike trip is possible if a source is connected to a destination. Each source and each destination can be used in at most one trip. Determine the maximum number of source-to-destination bike trips that can be scheduled.

This problem can be modeled as a bipartite matching problem. A matching in a bipartite graph is a set of edges such that no two edges share a common vertex. The maximum number of bike trips is exactly the size of the maximum matching. One efficient algorithm to solve this problem is the Hopcroft–Karp algorithm, which runs in \(O(\sqrt{V}E)\) time.

Input Format: The first line contains two integers \(s\) and \(d\) indicating the number of sources and the number of destinations, respectively. The second line contains \(s\) space-separated strings representing the source labels. The third line contains \(d\) space-separated strings representing the destination labels. The fourth line contains an integer \(p\), the number of available bike paths. The following \(p\) lines each contain a pair of strings separated by a space, representing a bike path from a source to a destination.

Output Format: Output a single integer denoting the maximum number of bike trips possible.

inputFormat

The input is read from standard input (stdin) and has the following format:

<s> <d>
<source_1> <source_2> ... <source_s>
<destination_1> <destination_2> ... <destination_d>
<p>
<source_x> <destination_y>
... (p lines total)

For example:

3 3
S1 S2 S3
D1 D2 D3
4
S1 D1
S2 D1
S2 D2
S3 D3

outputFormat

Output a single integer to standard output (stdout) that is the maximum number of bike trips (i.e., the size of the maximum matching).

## sample

3 3
S1 S2 S3
D1 D2 D3
4
S1 D1
S2 D1
S2 D2
S3 D3

3