Make sets disjoint without emptying them Suppose you have a set of sets of integers. It's possible that some of the sets will overlap (i.e. sharing elements). You could get rid of the overlaps by deleting elements from the sets, but then some of them might end up empty; that would be a shame. Can we make all the sets disjoint without emptying any of them?

Note that in this situation, there's never any reason to leave multiple elements in a set, so this problem can always be solved by reducing each set to just one element. That's the version of the problem we're solving here.

The task

Write a program or function, as follows:

Input: A list of sets of integers.

Output: A list of integers, of the same length as the input, for which:


All integers in the output are distinct; and
Each integer in the output is an element of the corresponding set of the input.


Clarifications


You can represent a set as a list if you wish (or whatever's appropriate for your language), disregarding the order of elements.
You don't have to handle the case where no solution exists (i.e. there will always be at least one solution).
There might be more than one solution. Your algorithm must always produce a valid solution, but is allowed to be nondeterministic (i.e. it's OK if it picks a different valid solution each time it runs).
The number of distinct integers appearing in the input, n, will be equal to the number of sets in the input, and for simplicity, will be the integers from 1 to n inclusive (as their actual values don't matter). It's up to you whether you wish to exploit this fact or not.


Testcases

[{1,2},{1,3},{1,4},{3,4}] -&gt; [2,3,1,4] or [2,1,4,3]
[{1,3},{1,2,4},{2,3},{3},{2,3,4,5}] -&gt; [1,4,2,3,5]
[{1,3,4},{2,3,5},{1,2},{4,5},{4,5}] -&gt; [1,3,2,4,5] or [3,2,1,4,5] or [1,3,2,5,4] or [3,2,1,5,4]


Victory condition

A program requires an optimal time complexity to win, i.e. if an algorithm with a better time complexity is found, it disqualifies all slower entries. (You can assume that your language's builtins run as fast as possible, e.g. you can assume that a sorting builtin runs in time O(n log n). Likewise, assume that all integers of comparable size to n can be added, multiplied, etc. in constant time.)

Because an optimal time complexity is likely fairly easy to obtain in most languages, the winner will therefore be the shortest program among those with the winning time complexity, measured in bytes.
Jelly, 8 bytes

Œp⁼Q$ÐfḢ


Try it online!

Explanation

Œp⁼Q$ÐfḢ  Main Link
Œp        Cartesian Product of the elements; all possible lists
     Ðf   Filter; keep elements that are
  ⁼Q$     Equal to themselves uniquified
      Ḣ   Take the first one


Extremely inefficient. Asymptotic to ϴ(n^(n+1)) according to Misha Lavrov; I think it's right.