1789. The Most People and Posts With No Link Between Them

There are nl applicants and nr posts, and m lines each name an applicant and a post that applicant is qualified for.

Pick as many people and posts as possible so that no picked applicant is qualified for a picked post. Print how many you can pick in total, counting applicants and posts together.

## What most people try first

Taking the side that is bigger and stopping. One whole side is always pickable, since every listed pair has one endpoint on each side, so the method never returns something illegal and that is exactly why it survives the first few examples. It is still wrong. Take nl = 2, nr = 2 and the single pair 1-1. The bigger side gives 2, while {applicant 1, applicant 2, post 2} holds no listed pair at all and gives 3, because post 2 suits nobody and joining it costs nothing.

The second attempt is a greedy sweep that takes any vertex whose pairs are all already excluded. That is exactly as fragile as the greedy plan in problem 1786, and for the same reason: an early cheap choice can block two later ones.

## The complement of the obstruction

Call a set of vertices a BLOCK if every listed pair has at least one endpoint inside it. A set is pickable exactly when the vertices left out form a block, because a listed pair with neither endpoint in the block would have both endpoints picked. So the largest pickable set has size nl + nr minus the size of the smallest block, and the question becomes how small a block can be.

A block has to contain at least one endpoint of every pair in any set of pairs with no repeated endpoint, and those pairs are disjoint, so the smallest block is at least as big as the largest such set. Konig's theorem says the two are equal on a two-sided list. Problem 1788 constructs a block of exactly that size, which proves the equality in the direction that matters here.

## Why it is correct

Put msize for the size of the largest set of pairs with no repeated endpoint, which is what problem 1786 computes. The smallest block has size msize, so the answer is nl + nr - msize. Nothing else has to be built: the augmenting search already gives msize.

``` nl = 3, nr = 3, pairs: 1-1, 1-2, 2-2, 3-3

largest set of disjoint pairs: 1-1, 2-2, 3-3 so msize = 3 smallest block: posts 1, 2, 3 so 3 vertices answer: 3 + 3 - 3 = 3 for example applicants 1, 2, 3 ```

## The boundary that breaks a careless implementation

With m = 0 the answer is nl + nr, every vertex at once. An implementation that starts the count at the largest side and adds misses this. An applicant qualified for nothing is always pickable and a post nobody wants is always pickable, so isolated vertices are pure profit and must not be skipped.

## Cost

O(nl * m) for the augmenting search and O(1) afterwards. At nl = 1000 and m = 20000 that is 2 * 10^7 steps.

## Overflow

The answer is at most nl + nr, so at most 2000. No intermediate exceeds that.

Constraints - `1 ≤ nl ≤ 1000` - `1 ≤ nr ≤ 1000` - `0 ≤ m ≤ 20000` - `1 ≤ u ≤ nl` and `1 ≤ v ≤ nr` - the same pair may be listed more than once, and a repeat changes nothing - an applicant may be qualified for nothing and a post may suit nobody