1792. Who Is Certain of a Post

There are nl applicants and nr posts, and m lines each name an applicant and a post that applicant is qualified for. A PLAN is a set of pairs with no applicant and no post used twice, and a LARGEST plan is one of maximum size.

An applicant is GUARANTEED if every largest plan gives it a post. Print how many applicants are guaranteed and which ones.

## What most people try first

Running the augmenting search once and printing whoever it placed. That answers a different question. With two applicants both qualified for post 1 only, the largest plan has size 1, one applicant is placed and the other is not, but swap the two and the other largest plan places the other one. Neither is guaranteed, and the answer is the empty set while the single run prints applicant 1.

The second attempt is "guaranteed means the applicant has a post nobody else wants". That is sufficient and not necessary. With pairs 1-1, 1-2, 2-2 the largest plan has size 2 and must be {1-1, 2-2}, so applicant 1 is guaranteed even though both of its posts are wanted by someone.

The third is "guaranteed means placed in some largest plan". On the two applicants and one post above, both are placed in some largest plan and neither in every one. The two questions have different answers and problem 1793 asks the other one.

## Delete and remeasure

Applicant u is guaranteed exactly when deleting u and all its pairs makes the largest plan smaller.

If deleting u leaves the size at msize, that smaller graph has a plan of size msize which does not use u, and the same pairs form a largest plan of the original graph, so u is not guaranteed. If deleting u drops the size to msize - 1, then every plan of the original graph that avoids u has size at most msize - 1, so every largest plan uses u. The two directions together make it an exact test, not a heuristic.

Deleting u never raises the size, because every plan avoiding u is a plan of the original graph, and it never drops it by two, because removing u from a largest plan leaves a plan of size msize - 1 avoiding u.

## Doing it without rebuilding the graph

Run the augmenting search once for the baseline msize, then once more per applicant with that applicant skipped as a search root and never used as the holder of a post. Skipping a root is enough: an applicant that is never a root and holds nothing can never enter a chain, because a chain enters an applicant only through the post it holds.

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

baseline: plan 1-2, 2-1, size 2 delete applicant 1: 2-1 only, size 1 -> smaller, so 1 is guaranteed delete applicant 2: 1-1 or 1-2, 3-1 ... best is 1-2 with 3-1, size 2 -> unchanged, so 2 is not guaranteed delete applicant 3: 1-2, 2-1, size 2 -> unchanged, not guaranteed answer: 1 1 ```

## The boundary that breaks a careless implementation

With m = 0 the largest plan is empty, deleting anyone changes nothing, and the answer is 0 with nothing after it. A pair listed twice must count once, or the search will try the same post twice inside one chain. The marks on posts must be cleared before every applicant's chain and not once per deletion.

## Cost

nl + 1 runs of an O(nl * m) search, so O(nl^2 * m). At nl = 120 and m = 600 that is about 9 * 10^6 steps, which is why the limits here are far below problem 1786's.

## Overflow

Every number printed is an applicant index, at most 120, and the count is at most nl.

Constraints - `1 ≤ nl ≤ 120` - `1 ≤ nr ≤ 120` - `0 ≤ m ≤ 600` - `1 ≤ u ≤ nl` and `1 ≤ v ≤ nr` - the same pair may be listed more than once, and a repeat changes nothing - the limits are deliberately small, because the method here runs the search once per applicant