Deadlock detector

The lock monitor takes a snapshot of a stuck server: which thread holds which lock, and which thread is blocked waiting for which lock. Your job is to find a deadlock in it, if there is one.

Implement find_deadlock(holds: list[list[int]], waits: list[list[int]]) -> list[int].

• holds is a list of pairs [thread, lock]: thread holds lock. A lock has at most one holder; a thread may hold many locks.
• waits is a list of pairs [thread, lock]: thread is blocked waiting for lock. A thread waits for at most one lock.
• Build the wait-for graph: an edge T -> U when T waits for a lock that U holds. A thread waiting for a lock nobody holds has no edge (it gets the lock next).
• A deadlock is a cycle in this graph. A thread waiting for a lock it already holds is a deadlock of one thread.
• Return the cycle as a list of threads: start at its smallest thread id and follow the edges. If there are several cycles, return the one whose smallest thread id is smallest. If there is none, return [].

find_deadlock([[1, 10], [2, 20], [3, 30]], [[1, 20], [2, 30], [3, 10]])   # [1, 2, 3]
# 2 waits for lock 3 (held by 7), 7 waits for lock 1 (held by 5), 5 waits for lock 2 (held by 2)
find_deadlock([[5, 1], [2, 2], [7, 3]], [[7, 1], [5, 2], [2, 3]])          # [2, 7, 5]
find_deadlock([[1, 10]], [[2, 10], [3, 99]])                               # []  (3 waits for a free lock)
find_deadlock([[4, 8]], [[4, 8]])                                          # [4]

holds and waits have up to 10^5 pairs each; thread and lock ids are in 0..10^9.

⭐ Bonus: a speed test with 10^5 pairs earns a star in linear time.