1793. Which Pairings Are Still On the Table

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.

For each listed pair in input order, say whether SOME largest plan uses it.

## What most people try first

Running the search once and reporting the pairs it chose. That reports one largest plan. On 1-1, 1-2, 2-1, 2-2 the plan {1-1, 2-2} is largest and so is {1-2, 2-1}, so all four pairs are usable and a single run marks two of them.

The second attempt is "a pair is usable when both its endpoints are placed in some largest plan". That is necessary and not sufficient. On 1-1, 2-1, 2-2 applicant 2 and post 1 are each placed in the unique largest plan {1-1, 2-2}, yet the pair 2-1 is in no largest plan at all.

The third is to assume usability is a property of the two endpoints separately. It is a property of the pair, which is why the test has to force the pair in.

## Force it in and remeasure

Write base for the size of a largest plan. Pair u-v is usable exactly when deleting applicant u, post v and every pair touching either of them leaves a largest plan of size base - 1.

Forward: if some largest plan uses u-v, remove that pair from it; the rest avoids u and v entirely and has base - 1 pairs, so the deleted graph reaches base - 1. Backward: if the deleted graph has a plan of base - 1 pairs, adding u-v back gives base pairs with no repeated endpoint, since nothing in that plan touches u or v. That is a largest plan using u-v.

Deleting one applicant and one post drops the size by at most 2 and by at least 0, so the only values worth distinguishing are base - 1 and base - 2, and the test is a single comparison.

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

pair 1-1: delete applicant 1 and post 1 -> 2-2 survives, size 1 = base - 1 usable pair 2-1: delete applicant 2 and post 1 -> nothing survives, size 0 not usable pair 2-2: delete applicant 2 and post 2 -> 1-1 survives, size 1 = base - 1 usable output: 101 ```

## Why repeats are harmless

Two identical lines ask the same question and must get the same character, which the test gives automatically because it depends on u and v only. Inside the search, though, the adjacency must be de-duplicated, or one chain will try the same post twice and the marks will be wasted.

## The boundary that breaks a careless implementation

Deleting the post must not mean rebuilding the adjacency. Mark the post as already used before every chain of that run, which has the same effect: no chain can ever reach it, so no plan of that run can use it.

A pair whose applicant and post are both otherwise unconstrained is always usable, so a long run of 1 characters is not evidence of a bug. The input guarantees m >= 1, so the output is never empty.

## Cost

m + 1 runs of an O(nl * m) search, so O(nl * m^2). At nl = 100 and m = 300 that is about 9 * 10^6 steps.

## Overflow

The output is a string of m characters, at most 300 of them, and every intermediate is a plan size, at most 100.

Constraints - `1 ≤ nl ≤ 100` - `1 ≤ nr ≤ 100` - `1 ≤ m ≤ 300` - `1 ≤ u ≤ nl` and `1 ≤ v ≤ nr` - the same pair may be listed more than once, and both lines get the same character - the limits are deliberately small, because the method here runs the search once per listed pair