def solution(nodeinfo):
    coords = {}
    levels = {}
    ids = {}
    for id, [x, y] in enumerate(nodeinfo):
        if y not in levels:
            levels[y] = []
        levels[y] += [x]
        ids[(x, y)] = id+1
        coords[id+1] = (x, y)
    for y in levels:
        levels[y] = sorted(levels[y])
    # print(levels)
    # print(ids)

    root_y = max(levels.keys())
    root_x = levels[root_y][0]
    root_id = ids[(root_x, root_y)]
    tree = {root_id: [None, None, None]} # left, right, head
    windows = {(-1, root_x): -root_id, (root_x, 100001): +root_id} # -: left range, +: right range
    for node_y in sorted(levels.keys(), reverse=True):
        next_windows = {}
        if node_y == root_y:
            continue
        for node_x in levels[node_y]:
            node_id = ids[(node_x, node_y)]
            for left, right in windows:
                if left < node_x and node_x < right:
                    parent_id = windows[(left, right)]
                    is_left = parent_id < 0
                    parent_id = abs(parent_id)
                    if is_left:
                        tree[parent_id][0] = node_id
                        next_windows[(left, node_x)] = -node_id
                        next_windows[(node_x, coords[parent_id][0])] = +node_id
                    else:
                        tree[parent_id][1] = node_id
                        next_windows[(coords[parent_id][0], node_x)] = -node_id
                        next_windows[(node_x, right)] = +node_id
                    tree[node_id] =[None, None, parent_id]
        windows = next_windows
    # print()
    # print('tree', tree)
    # print()
    
    preorder = []
    queue = [root_id]
    while len(queue) > 0:
        node = queue.pop(0)
        if node is None:
            continue
        preorder += [node]
        left, right, parent = tree[node]
        queue = [left, right, *queue]

    postorder = [0]
    stack = [root_id]
    while len(stack) > 0:
        node = stack[-1]
        left, right, parent = tree[node]
        if postorder[-1] == left or postorder[-1] == right:
            postorder += [node]
            stack.pop()
            continue
        if left is None and right is None:
            stack.pop()
            postorder += [node]
            continue
        if right is not None:
            stack += [right]
        if left is not None:
            stack += [left]
                
    return [preorder, postorder[1:]]