Place the fewest guards on an agent's risky calls

Agent buildHard40 min

Your task

Your agent's risky calls each pair one tool with one resource. A guard can wrap a tool, and then it checks every call made with that tool. Or it can wrap a resource, and then it checks every call that touches that resource. Each guard is code your team has to write and keep, so you want as few as will cover every risky call.

Write place_guards(tool_count, resource_count, calls) that returns where the guards go.

Input and output:

tool_count, resource_count: 1 to 500 each. Tools are numbered from 0, and so are resources.
calls: up to 5,000 pairs [tool, resource]. A pair can repeat.
Return [tools, resources]: the tools that get a guard and the resources that get a guard, each list in increasing order.

Rules:

A call is covered when its tool or its resource has a guard, and every call must be covered.
Use the smallest total number of guards.
A guard on a resource takes more work than a guard on a tool, so among placements with that smallest total, use the fewest guards on resources. These rules always leave exactly one placement.

Examples

place_guards(tool_count: int, resource_count: int, calls: list[list[int]]) -> list[list[int]]

Example 1

Inputplace_guards(3, 3, [[0, 0], [0, 1], [0, 2], [1, 0], [2, 0]])

Output[[0], [0]]

Example 2

Inputplace_guards(2, 2, [[0, 0], [1, 1]])

Output[[0, 1], []]

Example 3

Inputplace_guards(4, 3, [[0, 0], [1, 0], [2, 0], [3, 1], [3, 2], [2, 1]])

Output[[2, 3], [0]]