Drawing 5 elements uniformly from a list of lists

There's some context to this, so bear with me please.

I have a list of lists, call it nested_lists, where each list is of the form [[1,2,3,...], [4,3,1,...]] (i.e. each list contains two lists of integers). Now, in each of these lists, the two lists of integers have the same length and two integers corresponding to the same index represent a coordinate in R^2. So for example, (1,4) would be one coordinate from the above example.

Now, my task is to draw 5 unique coordinates from nested_lists uniformly (i.e. each coordinate has the same probability of being chosen), without replacement. That is, from all of the coordinates from the lists in nested_lists, I am trying to draw 5 unique coordinates uniformly without replacement.

One very straightforward way to do this would be to : 1. Create a list of ALL the unique coordinates in nested_lists. 2. Use numpy.random.choice to sample 5 elements uniformly without replacement. The code would be something like this:

import numpy as np
coordinates = []
#Get list of all unique coordinates
for list in nested_lists:
    
    l = len(list[0])
    for i in range(0, l):
        
        coordinate = (list[0][i], list[1][i])
        if coordinate not coordinates:
            coordinates += [coordinate]

draws = np.random.choice(coordinates, 5, replace=False, p= [1/len(coordinates)]*len(coordinates))

But getting a set of all the unique coordinates can be very computationally expensive, especially if nested_lists contains millions of lists, each with thousands of coordinates in them. So I'm looking for methods to perform the same draws without having to get a list of all the coordinates first.

One method I thought of would be to sample with weighted probabilities from each list in nested_lists. So get a list of the sizes (number of coordinates) of each list, and then go through each list and draw a coordinate with probability (size/sum(size))*(1/sum(sizes)). Repeating the process until 5 unique coordinates are drawn should then correspond to what we wanted to draw. The code would be something like this:

no_coordinates = lambda x: len(x[0])
sizes = list(map(no_coordinates, nested_lists))
i = 0
sum_sizes = sum(sizes)
draws = []
while i != 5:                           #to make sure we get 5 draws

    for list in nested_lists:
      
        size = len(list[0])
        p = size/(sum_sizes**2)
        for j in range(0, size):
            
            if i >= 5:                        exit for loop when we reach 5 draws
                break
            if np.random.random() < p and (list[0][j], list[1][j]) not in draws:
                draws += (list[0][j], list[1][j])
                i += 1
            
            

The code above seems to be more computationally efficient, but I am not sure if it actually draws with the same probability that would be required overall. From my calculation, the overall probability would sum(size)/sum_sizes**2 which is the same as 1/sum_sizes (our required probability), but again, I'm not sure if this is correct.

So I was wondering if there are more efficient approaches to drawing like I want, and if my approach is actually correct or not.