How can I generate random (not necessairly binary) tree?

I'm learning data structers and trying to write program, which would generate me a tree (not necessarily binary one) that contains n vertices. So far I tried Prufer sequence and it works for me well - it's very interesting solution of a problem. I found paper with Fast Random Tree Generating Algorithm (page 881-882).

Actually, I don't really care about speed of generation, but this method should be faster than generating tree from Prufer sequence. I wrote code to generate it, and I am not sure if it works correctly. Something is wrong with my code, or with the method presented in the above paper. Below I show what I produced. Code is written in Python3. Note that I changed indexing as Python is 0-indexed.

import random


def fast_random_tree(n):
    """
    https://link.springer.com/content/pdf/10.1007/3-540-44862-4_95.pdf
    """
    I = list(range(n))  # Initial vector of node numbers
    root = random.randint(0, n - 2)  # choosing root
    I[root], I[-1] = I[-1], I[root]  # replacing with last value
    edges = [None for _ in range(n - 1)]
    for m in range(n - 1):
        t = random.randint(0, m)  # new node
        s = random.randint(m + 1, n - 1)
        edges[m] = (I[t], I[s])  # adding edgde 
        I[t], I[n - m - 1] = I[n - m - 1], I[t]  # replaceing from n-m+1 to n - nodes that are in a tree already

    return edges


if __name__ == '__main__':
    edges = fast_random_tree(5)
    print(edges)

Sometimes I receive set of edges that does not create tree, because it contains cycles or graph is not fully connected. Example:

>>> print(fast_random_tree(5))
[(0, 4), (0, 3), (1, 2), (2, 1)]

  0      1
 / \     |
4   3    2

which is obviously not a tree. What also concerns me is that root is choosen randomly and moved to last position in array, but it can never be connected to some other vertice.

Do I forget about something or just this algorithm does not work? If you know other algorithms to generate a random tree I would love to read about it. Thanks for any help in advance!