Given a bipartite graph with no duplicate edges, find the size of the minimum vertex cover of the graph that uses at most $\textbf{two}$ vertices from the right side and any number of vertices from the left side.
See the notes for the explanation of the terminology.
The first line contains three integers $n$, $m$, $k$ $(1 \leq n,m,k \leq 10^5)$, the number of nodes on the left side, the number of nodes on the right side, and the number of edges respectively.
The next $k$ lines contain two integers each $l_i$, $r_i$ $(1 \leq l_i \leq n, 1 \leq r_i \leq m)$, the number of the node on the left side and the number of the node on the right side connected by the $i_{th}$ edge respectively.
Output a single integer $s$, the size of the minimum vertex cover of the graph.
A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$. You can read more $\href{https://en.wikipedia.org/wiki/Bipartite_graph}{here}$.
A vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
A minimum vertex cover is a vertex cover of the smallest possible number of nodes in it. You can read more $\href{https://en.wikipedia.org/wiki/Vertex_cover}{here}$.
Input | Output |
---|---|
3 2 2 1 2 1 1 Copy
|
1 Copy
|
4 3 5 1 1 1 3 1 2 3 3 2 2 Copy
|
3 Copy
|