Cooks Who Would Rather Swap

A catering school places n cooks in n restaurant kitchens, one cook per kitchen. Both sides have opinions:

• cook_prefs[c] lists the kitchens from cook c's favourite to least favourite (every kitchen appears once);
• kitchen_prefs[k] lists the cooks from kitchen k's favourite to least favourite (every cook appears once).

A placement is given as match, where cook c works in kitchen match[c] (every kitchen gets exactly one cook).

A cook c and a kitchen k that are not placed together form a blocking pair when both would rather be together than where they are now: cook c lists k before match[c], and kitchen k lists c before the cook it was given. Such a pair would quietly break the placement. A placement with no blocking pair is called stable.

Write blocking_pairs(cook_prefs, kitchen_prefs, match) that returns the list of all blocking pairs (c, k), sorted by c and then by k. Return [] when the placement is stable.

Examples

Input:  cook_prefs    = [[0, 1, 2], [0, 2, 1], [1, 0, 2]]
        kitchen_prefs = [[1, 0, 2], [0, 2, 1], [2, 1, 0]]
        match = [0, 1, 2]
Output: [(1, 0), (2, 1)]
Explanation: cook 1 likes kitchen 0 best, and kitchen 0 likes cook 1 more than cook 0,
whom it was given. Cook 2 prefers kitchen 1 to kitchen 2, and kitchen 1 prefers cook 2 to cook 1.

Input:  the same lists, match = [1, 0, 2]
Output: []

Goals

• Read preference lists for both sides of a two-sided market
• Test every unmatched cook-kitchen pair for a mutual wish to leave their partners
• Turn a preference list into a rank lookup so comparisons are one step