Fastest way to randomly sample N elements from a Python list with exclusions

Say I have a list of 20 unique numbers and I want to randomly sample N = 3 numbers from the list. For each number, there is the limitation that it cannot be in the final sample with some other numbers, given in a dictionary exclusions.

lst = list(range(20))
N = 3
exclusions = {0: [5], 1: [3, 13], 2: [10], 3: [1, 4, 18],
              4: [3, 15, 17, 19], 5: [0], 6: [12], 7: [13, 15],
              8: [10], 9: [16], 10: [2, 8, 12], 11: [15],
              12: [6, 10], 13: [1, 7], 14: [], 15: [4, 7, 11],
              16: [9], 17: [4], 18: [3], 19: [4]}

Right now I am using trial-and-error:

import random
sample = {random.choice(lst)}
n_sample = 1
while n_sample < N:
    s = random.choice([x for x in lst if x not in sample])
    if not set(exclusions[s]).isdisjoint(sample):
        sample.add(s)
        n_sample += 1

print(sample)
# {10, 2, 12}

However, this is super inefficient and cannot catch the case when there is no solution at all, especially when N is large. Can anyone suggest an efficient way to do this in Python?