1790. Everyone Mentioned At Least Once, With the Fewest Pairs

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

Choose as few of the listed pairs as possible so that every applicant appears in at least one chosen pair and every post appears in at least one chosen pair. An applicant may appear in several chosen pairs and so may a post, which is the difference from problem 1786. Print how many pairs you need, or -1 if no choice works.

## When it is impossible, and why that is the only way

If some applicant is qualified for nothing, no pair mentions it and no choice can cover it. The same holds for a post nobody is qualified for. If every vertex appears in at least one pair, then taking ALL m pairs covers everything, so a choice exists. So the answer is -1 exactly when some vertex has degree 0, and that is one pass over the input.

## What most people try first

Taking a largest set of pairs with no repeated endpoint and stopping, which is problem 1786's answer. On 1-1, 2-1, 2-2 that is {1-1, 2-2}, which happens to cover everything, so the method looks right. Add applicant 3 with the single pair 3-1 and the largest disjoint set is still 2, while the answer is 3: a disjoint set never covers more than 2 * msize vertices, and here there are 6.

The second attempt is one pair per applicant, ignoring the posts. On nl = 1, nr = 3 with pairs 1-1, 1-2, 1-3 that gives 1 and the true answer is 3, because each of the three posts needs a pair of its own.

## Pay for the pairing, then one pair per leftover vertex

Take a largest set of pairs with no repeated endpoint, msize of them. They cover 2 * msize distinct vertices. Every vertex they miss still has at least one pair of its own, by the impossibility test above, so give each missed vertex one such pair. That is msize + (nl + nr - 2 * msize) pairs, which is nl + nr - msize.

## Why nothing smaller works

Take any valid choice of c pairs and look at the graph made of those pairs only. It touches all nl + nr vertices and has c edges, and each of its connected pieces is connected, so a piece with k vertices carries at least k - 1 edges. Summing over the pieces, c >= nl + nr - p where p is the number of pieces. Each piece has at least one edge, and picking one edge per piece gives p pairs with no repeated endpoint, so p <= msize. Therefore c >= nl + nr - msize, which the construction attains.

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

largest disjoint set: 1-1, 2-2 msize = 2, covering 1, 2 and 1, 2 missed vertices: applicant 3 add one pair for it: 3-1 answer: 3 + 2 - 2 = 3 ```

## The boundary that breaks a careless implementation

With m = 0 and any nl, the answer is -1, not 0. A post listed twice by the same applicant is still one post, and a pair listed twice is still one pair for the purpose of the count, so the degree test must be a presence test rather than a count.

## Cost

O(nl * m) for the augmenting search, plus one pass to test the degrees.

## Overflow

The answer is at most nl + nr, so at most 2000.

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 choosing it twice is pointless so a repeat changes nothing - an applicant may be qualified for nothing and a post may suit nobody, and either makes the answer `-1`