import typing


def compute_parent(
    tour_edges: typing.List[int],
) -> typing.List[typing.Optional[int]]:
    """Compute parent from Euler-tour-on-edges.

    Args:
        tour_edges (typing.List[int]): euler tour on edges.

    Returns:
        typing.List[typing.Optional[int]]:
            parent list.
            the tour root's parent is None.

    Examples:
        >>> tour_edges = [0, 1, 4, -5, 2, -3, -2, 3, -4, -1]
        >>> compute_parent(tour_edges)
        [None, 0, 1, 0, 1]
    """
    n = len(tour_edges) >> 1
    parent: typing.List[typing.Optional[int]] = [None] * n
    st = [tour_edges[0]]
    for u in tour_edges[1:]:
        if u < 0:
            st.pop()
            continue
        parent[u] = st[-1]
        st.append(u)

    return parent