from math import ceil
 
N = 9
arr = [i for i in range(0, N)]
nodes = set((i, i + 1) for i in range(N - 1))
print(arr, nodes)
 
def func(start, end):
    print("start, end: ", start, end)
    if end - start <= 4:
 
        for i in range(start + 1, end + 1):
            if (start, i) not in nodes:
                nodes.add((start, i))
 
        for i in range(end - 1, start - 1, -1):
 
            if (i, end) not in nodes:
                nodes.add((i, end))
 
        return [start, end]
 
    n = end - start + 1
    k = int(n**0.5)
    size = int(n / k)
    lst = []
 
    for i in range(k):
        lst.extend(func(start, start + size - 1))
        start += size
 
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if (i, j) not in nodes:
                nodes.add((i, j))
 
    return lst
 
func(0, N - 1)
print(nodes)
 
print("No. new nodes added:", len(nodes) - (N - 1))

ZnJvbSBtYXRoIGltcG9ydCBjZWlsCgpOID0gOQphcnIgPSBbaSBmb3IgaSBpbiByYW5nZSgwLCBOKV0Kbm9kZXMgPSBzZXQoKGksIGkgKyAxKSBmb3IgaSBpbiByYW5nZShOIC0gMSkpCnByaW50KGFyciwgbm9kZXMpCgpkZWYgZnVuYyhzdGFydCwgZW5kKToKICAgIHByaW50KCJzdGFydCwgZW5kOiAiLCBzdGFydCwgZW5kKQogICAgaWYgZW5kIC0gc3RhcnQgPD0gNDoKICAgICAgICAKICAgICAgICBmb3IgaSBpbiByYW5nZShzdGFydCArIDEsIGVuZCArIDEpOgogICAgICAgICAgICBpZiAoc3RhcnQsIGkpIG5vdCBpbiBub2RlczoKICAgICAgICAgICAgICAgIG5vZGVzLmFkZCgoc3RhcnQsIGkpKQoKICAgICAgICBmb3IgaSBpbiByYW5nZShlbmQgLSAxLCBzdGFydCAtIDEsIC0xKToKCiAgICAgICAgICAgIGlmIChpLCBlbmQpIG5vdCBpbiBub2RlczoKICAgICAgICAgICAgICAgIG5vZGVzLmFkZCgoaSwgZW5kKSkKICAgICAgICAKICAgICAgICByZXR1cm4gW3N0YXJ0LCBlbmRdCgogICAgbiA9IGVuZCAtIHN0YXJ0ICsgMQogICAgayA9IGludChuKiowLjUpCiAgICBzaXplID0gaW50KG4gLyBrKQogICAgbHN0ID0gW10KCiAgICBmb3IgaSBpbiByYW5nZShrKToKICAgICAgICBsc3QuZXh0ZW5kKGZ1bmMoc3RhcnQsIHN0YXJ0ICsgc2l6ZSAtIDEpKQogICAgICAgIHN0YXJ0ICs9IHNpemUKICAgIAogICAgZm9yIGkgaW4gcmFuZ2UobGVuKGxzdCkpOgogICAgICAgIGZvciBqIGluIHJhbmdlKGkgKyAxLCBsZW4obHN0KSk6CiAgICAgICAgICAgIGlmIChpLCBqKSBub3QgaW4gbm9kZXM6CiAgICAgICAgICAgICAgICBub2Rlcy5hZGQoKGksIGopKQoKICAgIHJldHVybiBsc3QKCmZ1bmMoMCwgTiAtIDEpCnByaW50KG5vZGVzKQoKcHJpbnQoIk5vLiBuZXcgbm9kZXMgYWRkZWQ6IiwgbGVuKG5vZGVzKSAtIChOIC0gMSkp