1787. Print the Plan, Not Just Its Size

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

Print the size of a largest set of pairs with no repeated endpoint, then which post each applicant ends up with.

## The answer is not unique, so the procedure is pinned

On 1-1, 1-2, 2-1 both {1-2, 2-1} and {1-1} are valid plans and only the first is largest, but on 1-1, 1-2, 2-1, 2-2 both {1-1, 2-2} and {1-2, 2-1} are largest, and the two give different output lines. So the statement fixes exactly one of them.

> Keep a table saying which applicant holds each post, all posts free to begin > with. Take applicants 1, 2, ..., nl in that order. For applicant u, run > TRY(u) with an empty set of marked posts, where > > TRY(x): go through x's posts in INCREASING order, ignoring repeats in the > input. Skip any post already marked during this applicant's attempt. > Otherwise mark the post. If it is free, give it to x and succeed. If it is > held by y, call TRY(y), and if that succeeds give the post to x and > succeed. If the list runs out, fail. > > An applicant whose TRY fails is left without a post and is never > reconsidered.

Problem 1786 asks for the SIZE only, where no tie-break is needed.

## What most people try first

Printing whatever plan an arbitrary implementation produced. Two correct programs then disagree, and the problem has no answer. The order has to be part of the statement, which is why so much of the text above is procedure rather than mathematics.

The second mistake is marking posts once for the whole run instead of once per applicant. The marks exist to stop one applicant's search going round a cycle, and clearing them only at the start makes the second applicant refuse to look at a post the first merely passed through.

The third is taking a post away from y before knowing TRY(y) succeeded. The displacement must be written down only after the chain has found a free post.

## Why the procedure gives a LARGEST plan

The size claim is problem 1786's: a plan with no chain from any unplaced applicant to a free post is largest, because overlaying it with a larger plan leaves a path whose two ends are both unplaced in the smaller one, and that path is such a chain. Each TRY that succeeds raises the size by exactly one, since the displacements move applicants between posts and the only newly used post is the free one at the end of the chain.

The pinned order changes WHICH largest plan comes out, never whether it is largest, because the argument above never refers to the order.

## Why the marks make it finite

Within one applicant's attempt each post is marked at most once and a marked post is never revisited, so the chain visits at most nr posts and at most nr applicants, and the attempt ends.

``` input pairs: 1-1, 1-2, 2-1, 3-2

applicant 1: post 1 free -> post 1 goes to applicant 1 applicant 2: post 1 held by 1, mark it, TRY(1): post 1 marked, post 2 free -> applicant 1 moves to post 2, applicant 2 takes post 1 applicant 3: post 2 held by 1, mark it, TRY(1): post 1 held by 2, mark it, TRY(2): post 1 marked, list ends, fail -> applicant 3 is left out

output: 2 2 1 0 ```

## Cost

O(nl * m): one attempt per applicant, and an attempt inspects each qualification at most once. At nl = 1000 and m = 20000 that is 2 * 10^7 steps. The recursion in the statement is a description, not a requirement: an alternating chain can be nl applicants long and 1000 nested frames is at Python's recursion limit, so the reference solutions carry an explicit stack that walks the same order.

## Overflow

The size is at most min(nl, nr), so at most 1000, and every printed number is a post index or 0.

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 the procedure ignores the repeats - an applicant may be qualified for nothing and a post may suit nobody, so the graph may be disconnected